问题描述
给定一组整数序列,求出这组序列和中的最大值，不要求求出最大的子序列。
例如：
序列：-2 11 -4 13 -5 -2，则最大子序列和为20。
序列：-6 2 4 -7 5 3 2 -1 6 -9 10 -2，则最大子序列和为16
算法一
使用穷举法，代码如下：
[java]
package com.kiritor;
/**
* 使用穷举法就最大子序列问题
* 时间复杂度为O(N^3)
* @author Kiritor*/
public class MaxSub {
public static int maxSub(int a[])
{
int maxSum=0;
for(int i=0;i
int sum = 0;
for(int k=i;k<=j;k++)
{
sum+=a[k];
}
if(maxSum < sum)
maxSum = sum;
}
return maxSum;
}
}
package com.kiritor;
/**
* 使用穷举法就最大子序列问题
* 时间复杂度为O(N^3)
* @author Kiritor*/
public class MaxSub {
public static int maxSub(int a[])
{
int maxSum=0;
for(int i=0;i
int sum = 0;
for(int k=i;k<=j;k++)
{
sum+=a[k];
}
if(maxSum < sum)
maxSum = sum;
}
return maxSum;
}
}
显然这不是一个有效且合理的算法，算法的时间复杂度为O(N^3)，仔细思考就可以发现该
算法对于一些中间结果并未加以利用。例如：当i=0，j=3时计算了sum=a[0]~a[4]，但是当i=0,
j=4的时候计算sum的时候没有将a[0]~a[3]这一结果利用起来，而是重新再计算了一次，显然
做了一些无用功。
基于此算法进行改进，减少一重循环
算法二
对中间结果加以利用，降低算法的时间复杂度
[java]
package com.kiritor;
/**
* 对前面计算的结果加以利用
* 减去一层循环
* 时间复杂度降为O(N^2)
* @author Kiritor
*/
public class MaxSub {
public static int maxSub(int a[]) {
int maxSum = 0;
for (int i = 0; i < a.length; i++) {
int sum = 0;
for (int j = i; j < a.length; j++) {
sum += a[j];
if (maxSum < sum)
maxSum = sum;
}
}
return maxSum;
}
}
package com.kiritor;
/**
* 对前面计算的结果加以利用
* 减去一层循环
* 时间复杂度降为O(N^2)
* @author Kiritor
*/
public class MaxSub {
public static int maxSub(int a[]) {
int maxSum = 0;
for (int i = 0; i < a.length; i++) {
int sum = 0;
for (int j = i; j < a.length; j++) {
sum += a[j];
if (maxSum < sum)
maxSum = sum;
}
}
return maxSum;
}
}
算法三
对于这个问题我们可以使用分治的思想+递归来求解它，其时间复杂度就降低为O(NlogN)了
其主要的思想就是：
1、分解(分)：将原问题分解为若干个规模较小，相对独立，与原问题形式相同的子问题
2、解决：若子问题规模较小则直接解决，否则递归解决个子问题
3、合并(治)：将各子问题的解合并为原问题的解。
代码部分：
[java]
package com.kiritor;
/**
* 分治+递归的思想求解
* 时间复杂度降为O(NlogN)
* @author Kiritor
*/
public class MaxSub {
public int maxSub(int[] a,int left,int right)
{
if(left==right)
if(a[left]>0)
return a[left];
else
return 0;
int center = (left+right)/2;//分解
int maxLeftSum= maxSub(a,left,center);//左边递归
int maxRightSum = maxSub(a,center+1,right);//右边递归
//处理中间包含center左右边界的最大和情况
int maxLeftBorderSum = 0,leftBoderSum = 0;
for(int i=center;i>=left;i--)
{
leftBoderSum +=a[i];
if(maxLeftBorderSum
}
int maxRighttBorderSum = 0,rightBoderSum = 0;
for(int i=center+1;i<=right;i++)
{
rightBoderSum +=a[i];
if(maxRighttBorderSum
}
//问