Java求數組中連續n個元素使其和最大

給定一個數組，求出數組中連續的一些元素使其和的值最大。如果所有元素都為正數，顯然整個數組即為所求的。如果所有元素的值為負數，則所求的最大值為0.

這是在編程珠玑上看到的，其時間復雜度由O(n3)減為O(n)了。

java代碼

package　cn.lifx.test;

public　class　MaxSum
{
　 public　static　void　main(String[]　args)
　 {
　 int[]　arr　=　new　int[]{31,　-41,　59,　26,　-53,　58,　97,　-93,　-23,　84};

　 MaxSum　ms　=　new　MaxSum();

　 ms.Max(arr);
　 ms.Max2(arr);
　 ms.Max3(arr);

　 int　max　=　ms.Max4(arr,　0,　arr.length-1);
　 System.out.println("Max　sum　is　"　+　max);

　 ms.Max5(arr);
　 }

　 //方法1:　時間復雜度為O(n*n*n)
　 public　void　Max(int[]　arr)
　 {
　 int　max　=　0;
　 int　sum　=　0;
　 int　left　=　-1;
　 int　right　=　-1;

　 for(int　i=0;　i<arr.length;　i++)
　 {
　　 for(int　j=i;　j<arr.length;　j++)
　　 {
　　 sum　=　0;

　　 for(int　k=i;　k<=j;　k++)
　　 {
　　　 sum　=　sum　+　arr[k];
　　 }

　　 if(sum　>　max)
　　 {
　　　 left　=　i;
　　　 right　=　j;
　　　 max　=　sum;
　　 }
　　 }
　 }

　 if(right　>　0)
　 {
　　 System.out.println("Max　is　from　element　"　+　left　+　"("　+　arr[left]　+　")　to　element　"　+　right　+　"("　+　arr[right]　+　"),　max　sum　is　"　+　max);
　 }
　 else
　 {
　　 System.out.println("Max　sum　is　0　.");
　 }
　 }

　 //方法2：時間復雜度為O(n*n)
　 public　void　Max2(int[]　arr)
　 {
　 int　max　=　0;
　 int　sum　=　0;
　 int　left　=　-1;
　 int　right　=　-1;

　 for(int　i=0;　i<arr.length;　i++)
　 {
　　 sum　=　0;
　　 for(int　j=i;　j<arr.length;　j++)
　　 {
　　 sum　=　sum　+　arr[j];
　　 if(sum　>　max)
　　 {
　　　 left　=　i;
　　　 right　=　j;
　　　 max　=　sum;
　　 }
　　 }
　 }

　 if(right　>　0)
　 {
　　 System.out.println("Max　is　from　element　"　+　left　+　"("　+　arr[left]　+　")　to　element　"　+　right　+　"("　+　arr[right]　+　"),　max　sum　is　"　+　max);
　 }
　 else
　 {
　　 System.out.println("Max　sum　is　0　.");
　 }
　 }

　 //方法3：時間復雜度為O(n*n)
　 public　void　Max3(int[]　arr)
　 {
　 int　max　=　0;
　 int　sum　=　0;
　 int　left　=　-1;
　 int　right　=　-1;

　 int[]　temp　=　new　int[arr.length+1];

　 temp[0]　=　0;
　 for(int　i=0;　i<arr.length;　i++)
　 {
　　 temp[i+1]　=　temp[i]　+　arr[i];
　 }

　 for(int　i=0;　i<arr.length;　i++)
　 {
　　 for(int　j=i;　j<temp.length;　j++)
　　 {
　　 sum　=　temp[j]　-　temp[i];
　　 if(sum　>　max)
　　 {
　　　 left　=　i;
　　　 right　=　j-1;
　　　 max　=　sum;
　　 }
　　 }
　 }

　 if(right　>　0)
　 {
　　 System.out.println("Max　is　from　element　"　+　left　+　"("　+　arr[left]　+　")　to　element　"　+　right　+　"("　+　arr[right]　+　"),　max　sum　is　"　+　max);
　 }
　 else
　 {
　　 System.out.println("Max　sum　is　0　.");
　 }
　 }

　 //方法4：時間復雜度為O(n*logn)
　 public　int　Max4(int[]　arr,　int　left,　int　right)
　 {
　 int　sum　=　0;
　 int　max　=　0;
　 int　max1　=　0;
　 int　max2　=　0;
　 int　middle　=　0;

　 if(left　>　right)
　 {
　　 return　0;
　 }
　 else　if(left　==　right)
　 {
　　 return　(arr[left]　>　0　?　arr[left]　:　0);
　 }

　 middle　=　(left　+　right)/2;

　 for(int　i=middle;　i>=left;　i--)
　 {
　　 sum　=　sum　+　arr[i];
　　 if(sum　>　max1)
　　 {
　　 max1　=　sum;
　　 }
　 }

　 sum=0;
　 for(int　i=middle+1;　i<=right;　i++)
　 {
　　 sum　=　sum　+　arr[i];
　　 if(sum　>　max2)
　　 {
　　 max2　=　sum;
　　 }
　 }

　 max　=　max1+max2;
　 int　temp1　=　Max4(arr,　left,　middle);
　 int　temp2　=　Max4(arr,　middle+1,　right);

　 if(temp1　>　max)
　 {
　　 max　=　temp1;
　 }

　 if(temp2　>　max)
　 {
　　 max　=　temp2;
　 }

　 return　max;
　 }

　 //方法5：時間復雜度為O(n)
　 public　void　Max5(int[]　arr)
　 {
　 int　max1　=　0;
　 int　max2　=　0;
　 int　left　=　-1;
　 int　right　=　-1;
　 int　temp　=　0;

　 for(int　i=0;　i<arr.length;　i++)
　 {
　　 temp　=　(max1+arr[i]);
　　 if(temp　>　0)
　　 {
　　 max1　=　temp;
　　 }
　　 else
　　 {
　　 left　=　i+1;
　　 max1　=　0;
　　 }

　　 if(max1　>　max2)
　　 {
　　 right　=　i;
　　 max2　=　max1;
　　 }
　 }

　 if(right　>　0)
　 {
　　 System.out.println("Max　is　from　element　"　+　left　+　"("　+　arr[left]　+　")　to　element　"　+　right　+　"("　+　arr[right]　+　"),　max　sum　is　"　+　max2);
　 }
　 else
　 {
　　 System.out.println("Max　sum　is　0　.");
　 }
　 }
}

輸出為：

Java代碼

Max　is　from　element　2(59)　to　element　6(97),　max　sum　is　187
Max　is　from　element　2(59)　to　element　6(97),　max　sum　is　187
Max　is　from　element　2(59)　to　element　6(97),　max　sum　is　187
Max　sum　is　187
Max　is　from　element　2(59)　to　element　6(97),　max　sum　is　187