C++算法入门练习——最大连续子序列和
现有一个整数序列a1,a2,...,an，求连续子序列ai...aj，使得ai+...+aj最大。
输出三个整数，分别表示最大连续子序列和、满足该最大和的连续子序列和的首尾元素的下标i、j。
如果有多种满足条件的最优方案，那么输出首元素下标i最小的方案；如果还有多解，那么输出尾元素下标j最小的方案。
解题思路：
利用动态规划思想，当我们遇见一个新的元素后，我们只有两种状态选择：
①将这个元素与上一个进行拼接
②这个元素自己单独成为一个新的连续子序列和的开始。
而选择1还是2的条件为：上一个元素的dp数组是否大于等于0。如何理解这个条件呢？如果大于等于0，那么我们新加入元素，如果是正的，就能够使得这个连续子序列和变得更长，而如果是负的，并且负的程度远大于前面的，那么下一个元素，就会自立起新的门户，而上一个的dp值已经是暂时的最大值，如果负的程度比较小，说明可以接受，因为可以通过吸收更多正值来缓解这一个负值。
而为了记录序列开始的首下标，我们要用一个start数组进行回溯，去保存父亲结点，类似于并查集。
完整代码如下：
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int n;
cin>>n;
int dp[n];
int data[n];
for(int i=0;i<n;i++){
cin>>data[i];
}
dp[0] = data[0];
int start[n];
start[0] = 0;
for(int i=1;i<n;i++){
if(dp[i-1]>=0){
dp[i] = dp[i-1]+data[i];
start[i] = start[i-1];
}
else{
dp[i] = data[i];
start[i] = i;
}
}
int k = 0;
for(int i=1;i<n;i++){
if(dp[k]<dp[i]){
k = i;
}
}
cout<<dp[k]<<" "<<start[k]+1<<" "<<k+1<<endl;
return 0;
}