Max Sum Increasing Subsequence

• Time : O(n^2)
• Space : O(n)

#include <vector>
using namespace std;

vector<vector<int>> maxSumIncreasingSubsequence(vector<int> array) {
  int n = array.size(), ma = INT_MIN, tail = -1;
	vector<int> dp(n, 0), path(n, -1);
	map<int, int> mp;
	
	for(int i = 0; i < n; i++) {
		dp[i] = array[i];
		for(auto j = begin(mp); j != end(mp); j++) {
			auto num = j->first, pos = j->second;
			if(num >= array[i]) break;
			if(dp[i] < dp[pos] + array[i]) {
				dp[i] = dp[pos] + array[i];
				path[i] = pos;
			}
		}
		if(dp[i] > ma) {
			ma = dp[i];
			tail = i;
		}
		mp[array[i]] = i;
	}
	
	vector<int> res;
	while(tail != -1) {
		res.push_back(array[tail]);
		tail = path[tail];
	}

	reverse(begin(res),end(res));
  return {
      {ma}, // Sum of sequence.
      res,  // Elements of the sequence.
  };
}