最大连续子数组
给定一个数组A[0,1,…,n-1]，求A的连续子数组，使得该子数组的和最大。
例如:
数组：1，-2,3,10，-4,7,2，-5
最大字数组：3,10，，-4,7,2
此问题有以下四种方法
1、 暴力法
2、 分治法
3、 分析法
4、 动态规划法
暴力法
直接求解A[I,…j]的值，其中，0<=i<n，i<=j<n，因为i,i+1,…j的最大长度为n，所以时间复杂度O(n3)。
//暴力法int MaxSubArray(int *a, int n){int maxSum = a[0];int curSum;for(int i=0; i<n; ++i){for(int j=i; j<n; ++j){curSum = 0;for(int k=i; k<=j; ++k){curSum+=a[k];}if(curSum>maxSum)maxSum = curSum;}}return maxSum;}分治法
将数组从中间分开，那么最大子数组要么完全在左半边数组，要么完全在右半边数组，要么跨立在分界点上。
完全在左数组、右数组，递归可以解决
跨立在分界点上：实际上是左数组的最大后缀和右数组的最大前缀的和。因此，从分界点向前扫，向后扫即可。
//分治法
int maxAddSub(int *a, int from, int to){if(from==to)return a[from];int mid = (from + to) / 2;int m1 = maxAddSub(a,from,mid);int m2 = maxAddSub(a,mid+1,to);int now = a[mid], left = a[mid];int i;for(i=mid-1; i>=from; –i){now+=a[i];left = max(now,left);}int right = a[mid+1];now = a[mid+1];for(i=mid+2; i<=to; ++i){now+=a[i];right = max(now,right);}int m3 = left + right;return max(max(m1,m2),m3);}
分析法
设前缀和p[i]=a[0]+a[1]+a[2]+…+a[i]
s[i,j]=p[j]-p[i-1]，表示从数组第i个位置到第j个位置的元素和
算法过程：
遍历一遍数组，求前缀p[i]，0<=i<n，p[i]=p[i-1]+a[i]
再遍历一遍，找到最小的前缀p[i]，赋值给min
再遍历一遍各前缀，令p[i]-min最大，即是以a[i]结尾的数组中最大的子数组
因为该过程都是线性的，所以时间复杂度为O(N)
//分析法int maxAddSub(int *a, int n){vector<int> p;p.push_back(a[0]);int i;for(i=1; i<n; ++i)p.push_back(a[i]+p[i-1]);int min = 0;for(i=0; i<n; ++i)if(p[i]< min)min = p[i];int max = 0;for(i=0; i<n; ++i)if(p[i]-min > max)max = p[i]-min;return max;}动态规划
设S[i]为以a[i]结尾的数组中和最大的子数组，则S[i+1]=max(S[i]+a[i+1],a[i+1])，S[0]=a[0];
因此，遍历i:0<=i<n;
时间复杂度O(N);
//动态规划int MaxSubArray_dynamic(int *a, int n){int result = a[0];int sum = a[0];for(int i=0; i<n; ++i){if(sum>0)sum+=a[i];elsesum = a[i];if(sum > result)result = sum;}return result;}
测试代码// Maximum continuous word groups.cpp : Defines the entry point for the console application.//#include "stdafx.h"#include <iostream>#include <vector>using namespace std;//暴力法int MaxSubArray(int *a, int n){int maxSum = a[0];int curSum;for(int i=0; i<n; ++i){for(int j=i; j<n; ++j){curSum = 0;for(int k=i; k<=j; ++k){curSum+=a[k];}if(curSum>maxSum)maxSum = curSum;}}return maxSum;}int max(int a, int b){return a>b ? a : b;}//分治法int maxAddSub(int *a, int from, int to){if(from==to)return a[from];int mid = (from + to) / 2;int m1 = maxAddSub(a,from,mid);int m2 = maxAddSub(a,mid+1,to);int now = a[mid], left = a[mid];int i;for(i=mid-1; i>=from; –i){now+=a[i];left = max(now,left);}int right = a[mid+1];now = a[mid+1];for(i=mid+2; i<=to; ++i){now+=a[i];right = max(now,right);}int m3 = left + right;return max(max(m1,m2),m3);}//分析法int maxAddSub(int *a, int n){vector<int> p;p.push_back(a[0]);int i;for(i=1; i<n; ++i)p.push_back(a[i]+p[i-1]);int min = 0;for(i=0; i<n; ++i)if(p[i]< min)min = p[i];int max = 0;for(i=0; i<n; ++i)if(p[i]-min > max)max = p[i]-min;return max;}//动态规划int MaxSubArray_dynamic(int *a, int n){int result = a[0];int sum = a[0];for(int i=0; i<n; ++i){if(sum>0)sum+=a[i];elsesum = a[i];if(sum > result)result = sum;}return result;}int _tmain(int argc, _TCHAR* argv[]){int a[] = {1,-2,3,10,-4,7,2,-5};int size = sizeof(a)/sizeof(a[0]);double duration;cout<<MaxSubArray(a,size)<<endl;cout<<maxAddSub(a,0,size)<<endl;cout<<maxAddSub(a,size)<<endl;cout<<MaxSubArray_dynamic(a,size)<<endl;return 0;}
把你的脸迎向阳光，那就不会有阴影
