最大連續子向量和
一個整形數組，求其間連續的子向量，使其子向量的和最大。 如一組數組元素為 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 ;
}