2.14 动态规划 dynamic programming 之 求数组最大子数组之和
如要求 int A[]={a0,a1,a2,a3,a4}; 的最大子串之和，使用遍历所有子串的情况，复杂度达到o（n3）。而使用动态规划则可达到o（n）。
动态规划的思想是，把问题拆分为一个大的子问题和一个小的子问题，求解大的子问题需要用小子问题的结果。因此只需计算小子问题，就可以递推大问题，直到解决整个问题。
新浪面试题：10个阶梯，一次可以走1步或者2步，问有多少中走法？
答：考虑f(n)与f(n-1)的关系。如果最后一步是独立走一步完成的，则有f(n-1)*1种走法；如果最后一步是使用2步的话，则有f(n-2)种走法，先走到f(n-2)再使用2步走(剩下两步但不可以用两个1步，因为走一步的情况前面已经考虑了)。
因此f(n)=f(n-1)+f(n-2)，就是裴波那契数列，用DP方法可以以O(n)复杂度算出。
这个算法还有一个好处就是，不必把所有数据放入内存，只需存放K个数据就可以。
把a0和其他元素分为两组。则最大子串的情况有三种。1、a0是一个最大子串；2、最大子串从a1开始；3、最大子串从a1之后的元素开始。
设start[i]为从第i个元素开始的最大子串之和；all[i]为从第i个元素开始的最大子串之和(未必包括i元素)。
则可知all[i] = max ( A[i] , start[i+1] , all[i+1]) 对应上面三种情况。 因此从数组最后一个元素可以一直往前推，知道求出all[0]。
int max(int a,int b) { return (a>b) ? a : b; } int main() { int A[]={1,-2,3,5,-3,2}; int n=sizeof(A)/sizeof(int); //数组长度 int start[n]; //包含下标元素往右的最大连续子数组之和 int all[n]; //从下标到最右区间之中 存在的最大子数组之和 start[n-1]=A[n-1]; //从数组最后元素开始迭代，这两个初值是显而易见的。 all[n-1]=A[n-1]; for(int i=n-2;i>=0;--i) { start[i]=max(A[i],A[i]+start[i+1]);//理解：x1,x2,x3,x4,比如start[2]=x2+x3,证明从2开始的所有组合中，x2+x3是最大的，x2或x2+x3+x4 all[i]=max(start[i],all[i+1]); //都不是最大。再考虑x1.从x1开始的最大值，要不就start[2]+x1,要不就x1一个 } //因为如果这两种情况以外的start[1]=x1+x2+x3+x4<x1+x2+x3,因为x2+x3=start[2]>x2+x3+x4 cout<<all[0]<<endl; return 0; }
注意到start[i]是从start[i+1]迭代得来，all[i]又只是用了start[i]而没是用start[i+1],因此可直接用变量代替数组，节省内存。
int start=A[n-1],all=A[n-1]; for(int i=n-2;i>=0;--i) { start=max(A[i],A[i]+start); all=max(start,all); }
如果要求最大子串的位置呢？
需要把start和all的起止位置记录下来，用max对比时位置起止位置会发生改变，因此把max分为maxStart和maxAll。
int maxStart(int a,int b,int i,int &begin, int &end) { if(a>b) //A[i]>A[i]+start[i+1]时，start的起止位置改为i { begin=i; end=i; return a; } else //否则终点位置不改变，因为start的定义，起点位置必须变 { begin=i; return b; } //return (a>b) ? a : b; } int maxAll(int a,int b,int i,int &begin, int &end,int startBegin,int startEnd) { if(a>b) //如果all[i]是从i开始，则all的起止位置为start[i]的起止位置 { begin=startBegin; end=startEnd; return a; } else //否则all的起止位置跟上次一样，不做改变 { return b; } //return (a>b) ? a : b; } int main() { int A[]={-9,-2,-3,-5,-3}; int n=sizeof(A)/sizeof(int); //数组长度 int start=A[n-1],all=A[n-1]; int startBegin=n-1,startEnd=n-1,allBegin=n-1,allEnd=n-1;//start和all的起止下标。 for(int i=n-2;i>=0;--i) { start=maxStart(A[i],A[i]+start,i,startBegin,startEnd); all=maxAll(start,all,i,allBegin,allEnd,startBegin,startEnd); } cout<<all<<endl; for(int i=allBegin;i<=allEnd;++i) { cout<<A[i]<<" "; }cout<<endl; return 0; }
查找网页正文问题：
有一长度为n的数组 A，数组中所有元素已经确定，都为0或1求a，b使 ∑A[ i ] (from i = 0 to a-1) + ∑k*（1-A[ i ]） (from i = a to b) + ∑A[ i ] (from i = b+1 to n-1) 的值最大
k是一个已经确定的常数。这是一个动态规划的问题，求大神给个动态规划的递推公式。谢谢！！
使用动态规划的算法复杂度应为o(n)
int main() { int A[] = {0, 1, 0, 1, 0, 1, 0, 1, 1, 0}; double t= 5.0, nt = 5.0; double c = t / nt; int n=sizeof(A)/sizeof(int); //数组长度 double start[n]; //包含下标元素往右的最大连续子数组之和 double all[n]; //从下标到最右区间之中 存在的最大子数组之和 start[n-1]=t-A[n-1]+c*(1-A[n-1]); //从数组最后元素开始迭代，这两个初值是显而易见的。 all[n-1]=t-A[n-1]+c*(1-A[n-1]); for(int i=n-2;i>=0;--i) { start[i]=max(t-A[i]+c*(1-A[i]),start[i+1]+c*(1-A[i])-A[i]); all[i]=max(start[i],all[i+1]); } cout<<all[0]<<endl; return 0; } //注意还要把maxAll maxStart的参数和返回值修改为DOUBLE int main() { int A[] = {0, 1, 0, 0, 0, 0, 0, 1, 1, 0}; double t= 3.0, nt = 7.0; double c = t / nt; int n=sizeof(A)/sizeof(int); //数组长度 double start=t-A[n-1]+c*(1-A[n-1]); double all=t-A[n-1]+c*(1-A[n-1]); int startBegin=n-1,startEnd=n-1,allBegin=n-1,allEnd=n-1;//start和all的起止下标。 for(int i=n-2;i>=0;--i) { start=maxStart(t-A[i]+c*(1-A[i]),start+c*(1-A[i])-A[i],i,startBegin,startEnd); all=maxAll(start,all,i,allBegin,allEnd,startBegin,startEnd); } cout<<all<<endl; for(int i=allBegin;i<=allEnd;++i) { cout<<A[i]<<" "; }cout<<endl; return 0; }
2.5寻找最大的K个数
(1)新建一个长度为K的数组A，不断地把原数组的元素往里加。位置不够时，把A中最小的替换为新元素。（1、适用于数组长度非常巨大，不便多次遍历，此法只需遍历一次。2、可用堆存放K，用堆排序优化算法效率）
(2)找出第K大的数，然后自然可以找出前K大的数。P142
if(数组中大于mid的元素个数>=K) min=mid; else max=mid; //证明前K大的数在min到mid之间