using namespace std;
/*
问题：给定一个整数数组(有正数有负数)，找出总和最大的连续数列，并返回总和
分析：这个是动态规划问题，采用前缀和的方式来解决。
设dp[i]表示以元素A[i]结尾的最大连续子序列之和
最大连续子序列和的产生方式不过两种：
1】是通过以A[i-1]结尾的最大连续子序列之和 + A[i]形成的
2】前面A[i-1]结尾的最大连续子序列之和小于0，直接抛弃，重新选择A[i]作为最大连续子序列之和
所以有dp[i] = max{dp[i-1] + A[i] , A[i]}
dp[0] = A[0]
而且需要记录最大连续子序列之和的起始位置，设数组paths,
paths[i]表示以dp[i]结尾的最大连续子序列和的起始位置
输入:
9(数组元素个数n，下一行输入n个元素)
3 -4 5 7 -1 2 6 1 -13
输出:
20(最大连续子序列和)
5 7 -1 2 6 1(最大连续子序列)
*/
int maxSubsequenceSum(vector<int>& datas ,vector<int>& dp, vector<int>& paths , int& maxEndIndex)
{
if(datas.empty())
{
throw("No data");
}
int size = datas.size();
int max = INT_MIN;
int maxIndex = -1;
for(int i = 0 ; i < size ; i++)
{
if(i)
{
if( dp[i-1] <= 0 )
{
dp.at(i) = datas.at(i);
paths.at(i) = i;
}
else
{
dp.at(i) = dp.at(i-1) + datas.at(i);
paths.at(i) = i - 1;
}
}
else
{
dp.at(i) = datas.at(i);
paths.at(i) = i;
}
if(dp.at(i) > max)
{
max = dp.at(i);
maxIndex = i;
}
}
maxEndIndex = maxIndex;
return max;
}
void printPath(vector<int>& paths , int maxEndIndex , vector<int>& datas)
{
if(paths.empty())
{
return;
}
if(-1 == maxEndIndex)
{
return;
}
//如果递归后寻找的路径下标相同，说明应该截止了
if(-1 != maxEndIndex && maxEndIndex == paths[maxEndIndex])
{
cout << datas.at(maxEndIndex) << " ";
return;
}
int value = paths[maxEndIndex];
printPath(paths , value , datas);
cout << datas.at(maxEndIndex) << " ";
}
void process()
{
int num;
vector<int> datas;
vector<int> paths;
vector<int> dp;//存放最大连续子序列和
int value;
int maxEndIndex = 0;
while(cin >> num)
{
datas.clear();
paths.clear();
dp.clear();
for(int i = 0 ; i < num ; i++)
{
cin >> value;
datas.push_back(value);
paths.push_back(-1);
dp.push_back(0);
}
int result = maxSubsequenceSum(datas, dp , paths , maxEndIndex);
cout << result << endl;
printPath(paths , maxEndIndex , datas);
cout << endl;
}
}
int main(int argc , char* argv[])
{
process();
getchar();
return 0;
}