给定一个数组，求出数组中连续的一些元素使其和的值最大。如果所有元素都为正数，显然整个数组即为所求的。如果所有元素的值为负数，则所求的最大值为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