Java求数组中持续n个元素使其和最大[Java编程]

给定一个数组,求出数组中持续的一些元素使其和的值最大.假如全部元素都为正数,明显整个数组即为所求的.假如全部元素的值为负数,则所求的最大值为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