web123456

Programmer Interview Gold - Problem Solving Summary: 9.17 Medium Difficulties 17.8 Given an array of integers (both positive and negative), find the consecutive series that has the largest sum and return the sum

  • #include <iostream>
  • #include <>
  • #include <vector>
  • 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;
  • }