算法设计与分析算法实现——动态规划最大子段

输入：整数序列a1,a2,…,an
输出：序列的一个子段，其和Σak最大
注意：当所有整数都为负数时，定义最大子段和为0

使用动态规划，输入数组是a[n]；
状态转移方程dp[i]=max(dp[i-1]+a[i],a[i])——这个状态方程可以发现，使得满足“连续”这一要求的重点在于每个dp[i]都包含了当前元素a[i]；
使用两个数组start,end分别记录dp[i]的起始数组元素下标start[i]和dp[i]的终止数组元素下标end[i]——方便最后可以最大子段的每个元素；
使用max记录dp[i]的最大值，maxi_i记录下标；

//dp[i]=max{dp[i-1]+a[i],a[i]}
#include<iostream>
#include<vector>
using namespace std;
#define MAX  100000
int main() {int dp[MAX];//dp[i]表示前i的数（包含a[i]）的最大子段和int a[MAX];vector<int>start,end;//start[i],end[i]记录dp[i]的起始下标和终止下标int n;//数组a的长度cin >> n;bool flag = 0;//判断数组元素是不是全非正数for (int i = 0; i < n; i++) {cin >> a[i];if (a[i] > 0)//数组元素存在正数flag = 1;}if (flag == 0) {//如果数组a所有元素都是非正数，则输出0cout << 0 << endl;return 0;}dp[0] = a[0];//初始化dp[0],start[0],end[0]start.push_back(0);//end.push_back(0);//int max = 0xffffffff;//记录dp[i]的最值int max_i;//记录使得dp[i]取得最值的下标ifor (int i = 1; i < n; i++) {if (dp[i - 1] + a[i] > a[i]) {//状态转移方程dp[i] = dp[i - 1] + a[i];start.push_back(start[i - 1]);//随dp[i]更新start数组}else {dp[i] = a[i];start.push_back(i);}end.push_back(i);//随着dp[i]更新end数组if (dp[i] > max) {//寻找最大dp[i]max = dp[i];max_i = i;}}for (int i = start[max_i]; i <= end[max_i]; i++) {//输出最大子段cout << a[i] << " ";}return 0;
}