第三題
題目：
輸入一個整型數組，數組裡面有正數也有負數，數組中連續的一個或者多個數組成一個子數組，每個子數組都有一個和。
求，所有子數組的和的最大值。要求時間復雜度為O（n）
分析：
本題是一個典型的使用動態規劃算法的題目。
動態規劃算法的使用基本要素是1、最優子結構（當問題的最優解包含了其子問題的最優解，成該問題具有最優子結構性質）
2、重疊子問題（也就是說如果使用遞歸算法自頂朝下求解問題時，每次產生的子問題並不是新問題，有一些子問題被反復計算多次）。
對於本題，要求計算和最大的一個子數組，對於是不是最優子結構的分析，假設數組為a[] （size=n），那麼可以分割成為0-n-2和1-n-1兩個子問題。
這兩個子問題裡面又都包含1-n-2子問題，可以使用遞歸算法，但是由於使用遞歸算法會造成大量的子問題的求解，因此使用動態規劃算法。
動態規劃算法
設SUM[i]為前i個元素中，包含第i個元素且和最大的連續數組，result為已找到的子數組中最大的，對於第i+1個元素，有兩種選擇，1.作為新子數組的
第一個元素，2.放入前面找到的數組。
sum[i+1] = max(a[i+1],sum[i]+a[i+1]);
本題若使用順序求解算法 復雜度為O(n^2)，遞歸求解算法復雜度為O(nlogn)，動態規劃算法復雜度為O（n）
順序求解
遞歸求解
動態規劃
代碼：
[cpp]
#include<iostream>
using namespace std;
int maxSubArray(int *a, const int length)
{
int maxSumSubArray = 0;
int sum_i = 0;
for(int i=0; i <length; i++)
{
sum_i = sum_i + a[i];
if(sum_i < 0) sum_i = 0;
else
{
if(sum_i > maxSumSubArray) maxSumSubArray = sum_i;
}
}
//若是數組中的元素均為負值
if(sum_i==0)
{
for(int i=0; i < length; i++)
{
if(a[i] > maxSumSubArray) maxSumSubArray = a[i];
}
}
return maxSumSubArray;
}
int main()
{
int a[10] = {1, 3, -3, -4 ,5 ,-2, 6, -1, 2, -6};
int length = sizeof(a)/sizeof(int);
cout<<maxSubArray(a,length);
return 0;
}
