动态规划--最大子数组

原始问题input: 给定一个数组x[1 . . .n]对任意一对数组下标为l,r(lr)的非空子数组其和为S ( l , r ) ∑ i l r X [ i ] S(l, r) \sum_{il}^{r} X[i]S(l,r)∑ilr​X[i]output求出 MAX{ S(l , r) }(S m a x S_{max}Smax​)从后往前看在当前x [ i ] x[i]x[i],后面以x [ i 1 ] x[i1]x[i1]开头的最大数组之和如果他是大于0那加起来x [ i ] x[i]x[i]会更大若小于0那就更小规律证明D i 1 D_{i1}Di1​:以x[ ]开头的最大子数组和S i 1 S_{i1}Si1​:以x[ ]开头的任一子数组和(S i 1 D i 1 S_{i1}D_{i1}Si1​Di1​)D i 1 0 D_{i1}0Di1​0x [ i ] D i 1 x [ i ] S i 1 x[i]D_{i1}x[i]S_{i1}x[i]Di1​x[i]Si1​D i x [ i ] D i 1 D_ix[i]D_{i1}Di​x[i]Di1​D i 1 0 D_{i1}0Di1​0x [ i ] S i 1 X [ i ] D i 1 x [ i ] x[i]S_{i1}X[i]D_{i1}x[i]x[i]Si1​X[i]Di1​x[i]不如不加D i x [ i ] D_{i}x[i]Di​x[i]问题结构分析-递推关系建立-自底向上计算-最优方案追踪问题结构分析给出问题表示D [ i ] D[i]D[i]:以x [ i ] x[i]x[i]开头的最大子数组和明确原始问题S m a x m a x ( D [ i ] ) S_{max}max(D[i])Smax​max(D[i])(1in)递推关系建立分析最优子结构(D [ i ] D[i]D[i])D i 1 0 D_{i1}0Di1​0D i x [ i ] D i 1 D_ix[i]D_{i1}Di​x[i]Di1​D i 1 0 D_{i1}0Di1​0D i x [ i ] D_{i}x[i]Di​x[i]递推公式D [ i ] { x [ i ] D [ i 1 ] , D i 1 0 x [ i ] , D [ i 1 ] 0 D[i]\begin{cases}x[i]D[i1], D_{i1}0\\x[i], D[i1]0\end{cases}D[i]{x[i]D[i1],x[i],​Di1​0D[i1]0​自底向上计算初始化D [ n ] x [ n ] D[n]x[n]D[n]x[n]从后往前看最优方案追踪记录决策过程结尾相同(接着加了x [ i ] x[i]x[i],留着D [ i 1 ] D[i1]D[i1])R e c [ i ] R e c [ i 1 ] Rec[i]Rec[i1]Rec[i]Rec[i1]结尾不同(舍去了后面的D [ i 1 ] D[i1]D[i1])R e c [ i ] i Rec[i]iRec[i]i舍去之后当前的结尾就是i自己输出最优方案其实是整体扫了一遍最大子数组和有可能在每个地方从子问题中查找最优解最大子数组开头位置i最大子数组结尾位置R e c [ i ] Rec[i]Rec[i]就是从i——Reci示例代码Max-Continuous-Subarray-DP(, )input:数组x数组长度noutput:最大子数组和S m a x S_{max}Smax​和子数组起止位置lrintD[n],Rec[n];intres[3];intMax_Continuous_Subarray_DP(int*x,intn){//初始化D[n]x[n];Rec[n]n;//动态规划for(intin-1;i0;i){if(D[i1]0){D[i]x[i]D[i1];Rec[i]Rec[i1];}else{D[i]x[i];Rec[i]i;}}SmD[1];for(inti2;in;i){if(SmD[i]){SmD[i];li;rRec[i];}}res[0]Sm;res[1]l;res[2]r;returnres;}时间复杂度O(n),相当于每个扫了一遍