最大连续子数组和算法（动态规划解释）
之前在其他博客看到了，但是算法的关键部分完全看不懂为什么要这么做，直到最近上算法课，才终于知道到底怎么来的。
问题描述：
给出一个数组，求其最大连续子数组和
例：数组{1,2,3,4,-5,10,-1,-1}的最大连续子数组和是子数组{1,2,3,4,-5,10}的和15
算法过程：
这个算法能从零直接想出来的人是真的厉害，我并不可以，所以我直接描述一下这个算法是怎么算的，而不描述怎么想到的了
首先我们把原来数组记做a，然后最关键的一步，我们需要一个等长的数组b，b[j]的含义是以下一系列和中的最大值
a[0] + a[1] + a[2] + a[3] + … + a[j]
a[1] + a[2] + a[3] + … + a[j]
a[2] + a[3] + … + a[j]
a[3] + … + a[j]
……
a[j]那么显然可以知道的是，b数组中的最大值，就是我们想要的a的最大连续子数组和。
接下来就是要得到数组b，初始化的话，b[0]应该为0和a[0]之中的较大者，下面探讨b[j]和b[j+1]之间的关系：
b[j+1]只有两种取法，第一种是b[j]+a[j+1]，注意b[j]本身就是最大值，所以不用再去考虑b[j]内部的情况了，第二种是a[j+1]，所以
b[j+1] = max{ b[j]+a[j+1], a[j+1] }
OK，到此这个算法其实就算完成了，下面是直接根据这个思路打的代码：
#include <stdio.h>
#include <stdlib.h>
int main() {
int a[] = {1,2,3,4,-5,10,-1,-1}; // 原数组
int* b = (int*)malloc(sizeof(a)); // 数组b，和原数组等长
// 初始化
b[0]= a[0] > 0 ? a[0] : 0;
// 遍历构造，注意i的边界
int length = sizeof(a) / sizeof(int); // 数组长
for (int i = 0; i < length - 1; i++) {
b[i+1] = b[i] + a[i+1] > a[i+1] ? b[i] + a[i+1] : a[i+1];
}
// 然后找出b中的最大值
int max = b[0];
for (int i = 1; i < length; i++)
if (b[i] > max)
max = b[i];
printf("max=%i\n", max);
return 0;
}然后导致我一直看不懂的地方来了，对上面这段代码进行编程上的优化，优化主要有两个地方，
首先在上面的分析中，b[n+1]只和当前遍历到的a[n+1]和前一个b[n]直接相关，所以其实并不需要保存整个数组b，换用一个变量就可以了，其次是最大值，也是可以一遍遍历一边改的
于是就有了目前网络上流传最多的以下这种代码：
#include <stdio.h>
#include <stdlib.h>
int main() {
int a[] = {1,2,3,4,-5,10,-1,-1}; // 原数组
int max = 0;
int b = 0;
int length = sizeof(a) / sizeof(int); // 长度
for (int i = 0; i < length; i++) {
b = b + a[i] > a[i] ? b + a[i] : a[i];
max = max > b ? max : b;
}
printf("max=%i\n", max);
return 0;
}显然这个算法是o(n)时间复杂度的，讲真最近学动态规划基本o(n^3)起步。动态规划两个基本要素，首先最优子结构性质，全局最大值基于n个子问题b的最优解，而且可以看到b[j+1]是基于b[j]给出的，也就是一个问题是基于他的子问题的最优解来解决的，其次显然子问题是有交叉的，求解b[j]需要b[j-1]，递归一下就需要b[j-2]，由此就出现了交叉。
PS：LeetCode上题号53 最大子序和就是这个问题，但是貌似子数组长度不为0，所以初始化会有一点变化。