最大连续子向量和
一个整形数组，求其间连续的子向量，使其子向量的和最大。 如一组数组元素为 31 ， -41 ，59 ， 26 ，-53 ，58 ， 97 ， -93 ， -23 ， 84
【2 ， 6】之间的子向量之和最大。定义若数组中的元素全部为负数，则最大和值为0 。 若数组中的数字全部为正数，则最大和值即为数组中的全部元素之和。
解法一：
经过建模转换，即是求在[1,n]中 求[i,j]之和的最大值，使用暴力解法，算出任意[i,j]之间的各个值，然后取最大值，即为所求。
#include <iostream>
using namespace std ;
int sumMax(int *a , int n)
{
int max = 0 ,sum = 0 ; //
for(int i = 0 ; i < n ; i++)
{
sum = 0 ;
for(int j = i ; j < n ; j++)
{
sum += a[j] ;
if(max < sum)
{
max = sum ;
}
}
}
return max ;
}
int main()
{
int a[] = {31 , -41 ,59 , 26 ,-53 ,58 , 97 , -93, -23 , 84} ;
cout<<"max"<<sumMax(a , 8) ;
cin.get() ;
return 0 ;
}
解法二
第一种解法比较常见，但是此种解法则不常用。定义个数据S ，则S[i] 表示数组a[0]到a[i]之间的元素之和，那么S[j]-S[i] 的差值，表示
a[i]到a[j]之间和。 本题的问题，就是求S[j]-S[i]的最大值。
#include <iostream>
using namespace std ;
int sumMax(int * s , int n )
{
int sum = 0 , max = 0 ;
for(int i = 0 ; i < n ; i++)
{
for(int j = i + 1;j < n ;j++)
{
sum = s[j] - s[i] ;
if(sum > max)
max = sum ;
}
}
return max ;
}
int main()
{
int a[] = {31 , -41 ,59 , 26 ,-53 ,58 , 97 , -93, -23 , 84} ;
int * s = new int[8];
int sum = 0 ;
for(int i = 0 ; i < 8 ; i++)
{
sum += a[i] ;
s[i] = sum ;
}
cout<<"max"<<sumMax(s , 8);
delete [] s ;
cin.get() ;
return 0 ;
}
综上，以上的两种解法都是O（n*n）级别的，实质上可以使用分治法来解决此问题。
解法三：
利用分治法解决最大子序列和问题
可以将原数组从中间元素开始分成两个部分，左边部分最大子序列和为Ml，右边部分最大子序列和为Mr,还有一种情况即整个数组的
最大子序列和存在左右两个部分之间，记为Mc。 所求结果即为Ml 、Mr、Mc 三者的最大值。利用递归算法解决此问题。
/**//*
该算法使用了分治法，求最大子序列的和问题
*/
#include <iostream>
using namespace std ;
inline int Max(int , int) ;
int sumMax(int * a , int l , int r);
int main()
{
int a[] = {31 , -41 ,59 , 26 ,-53 ,58 , 97 , -93, -23 , 84} ;
cout<<sumMax(a , 0 , 9) ;
cin.get() ;
return 0 ;
}
inline int Max(int x , int y)
{
return x>y ? x : y ;
}
int sumMax(int * a , int l , int r)
{
if(l > r)
return 0 ;
if(l == r)
return Max(0 , a[l]) ;
//计算左部分的最大值
int m = (l + r) >> 1 ;
int lmax = 0 , sum = 0 ;
for(int i = m ; i >= 0 ; i--) //左部分从中间向左依次叠加，然后判断是否获得最大值
{
sum += a[i] ;
lmax = Max(sum , lmax) ; //左边最大值
}
int rmax = 0 ;
sum = 0 ;
for(int j = m + 1; j <= r ; j++)//右部分从中间向右依次叠加，然后判断是否获得最大值
{
sum += a[j] ;
rmax = Max(sum , rmax) ; //右边最大值
}
return Max(lmax + rmax , Max(sumMax(a , l , m) , sumMax(a , m + 1 , r) )) ;
}
第三个算法的时间复杂度为o(n * log(n)) ，通过这个题目来学习分治法。
第四种解法：
该解法为一线性解法，算法复杂度为O(n) ，定义maxEndingHere为截止到a[j]处的最大子数组之和，则a[j+1]处的最大子数组之和为
max(maxEndingHere + a[j + 1] , 0) ，而我们的所求maxSofar即为各个位置最大的maxEndingHere。
/**//*
通过线性算法解决问题
*/
#include <iostream>
using namespace std ;
inline int Max(int , int) ;
int sumMax(int a[] , int n) ;
int main()
{
int a[] = {31 , -41 ,59 , 26 ,-53 ,58 , 97 , -93, -23 , 84} ;
cout<<sumMax(a , 9) ;
cin.get() ;
return 0 ;
}
inline int Max(int x , int y)
{
return x>y ? x : y ;
}
int sumMax(int a[] , int n)
{
int maxEndingHere = 0 , maxSoFar = 0 ; //maxEndingHere 表示截止到位置i处的最大子序列和
for(int i = 0 ; i < n ; i++)
{
maxEndingHere = Max(maxEndingHere + a[i] , 0 ) ;
maxSoFar = Max(maxEndingHere , maxSoFar) ;
}
return maxSoFar ;
}