最大子数列和问题
给出一个数列，现在求其中一个子数列，要求是所有子数列的和的最大值。另外还有其他问法，例如给出一个数组，要求求出连续的元素和的最大值。可以一个例子来解释：
假设有数列：[-1,2,3,-5,6,-2,4]，那么总共有7^2=49种子数列，如果分别求和，其中最大的子数列为：[6,-2,4]，其和为8。
暴力求解
最暴力的算法是枚举，双重for循环，枚举所有的子数列。这样时间复杂度为O(n^2)，相对而言是比较慢的，但是是最简单的一种方法。
Kadane算法
首先安利一个youtube的视频，能翻墙以及能理解youtube自动尬翻的同学看这个是比较好的，讲的还可以，比较详细：
Kadane’s Algorithm to Maximum Sum Subarray Problem
最大子数列和问题的最优解就是Kadane算法，可以在O(n)的时间复杂度内解决问题，其思想实际是动态规划。
首先在定义状态的时候，我们声明dp[i]这个状态是指以i结尾的子数列中，最大和是多少。而因为有一个重要要求：子数列，所以求和的元素必须是连续的，那么有状态转移方程：
1
dp[i] = max(n[i],dp[i-1]+n[i]);
那么，如果我们设定一个指针，始终指向构造dp数组时的最大值，那么在遍历一次数列后，指针指向的值也就是最大值了。
C++ 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<iostream>
#define MAX 2333
using namespace std;
int n[MAX];
int dp[MAX];
int Max(int a,int b){
return a > b ? b : a;
}
int kadane(){
int ans = n[0];
dp[0] = n[0];
for(int i = 1;i < strlen(n);i++){
dp[i] = Max(n[i],dp[i-1]+n[i]);
ans = Max(dp[i],ans);
}
}
int main(){
// 自设例子
system("pause");
return 0;
}