using namespace std;
/*
Problem: Given an array of integers (with positive and negative numbers), find the consecutive series with the largest sum and return the sum
ANALYSIS: This is a dynamic programming problem and is solved using prefix sums.
Let dp[i] denote the sum of the largest consecutive subsequences ending with element A[i]
Maximum contiguous subsequence sums can be generated in no more than two ways:
1] is formed by the sum of the largest consecutive subsequences ending in A[i-1] + A[i]
2] The sum of the largest consecutive subsequence ending in the previous A[i-1] is less than 0, discard it directly and re-select A[i] as the sum of the largest consecutive subsequence
So we have dp[i] = max{dp[i-1] + A[i] , A[i]}
dp[0] = A[0]
And you need to record the starting position of the sum of the largest consecutive subsequence, set the array paths, the
paths[i] denotes the starting position of the largest consecutive subsequence sum ending in dp[i]
Input.
9 (number of array elements n, enter n elements on the next line)
3 -4 5 7 -1 2 6 1 -13
Output.
20 (maximum contiguous subsequence sum)
5 7 -1 2 6 1 (maximum contiguous subsequence)
*/
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 the recursive search path subscripts are the same, it means that it should be closed
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;//Store the largest consecutive subsequence and
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;
}