Maximum Sum Increasing Subsequence Editorial

Practice Problem Link: Maximum Sum Increasing Subsequence

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

A maximum sum subsequence of an array is a subsequence whose sum is maximum with the condition that the subsequence is sorted. Given an array, find the sum of the maximum sum subsequence of that array.

Naive Approach

The naive approach is to generate all the subsequences and check if it's sorted. Among the sorted subsequences, calculate the maximum sum.

Analysis

• Time Complexity: O(n * 2ⁿ)
• Space Complexity: O(n)

Implementation

C++

void getSubsets(vector<int> &A, int start, vector<int> &currSubset, vector<vector<int>> &allSubsets) {
	if (start == A.size()) {
		allSubsets.push_back(currSubset);
		return;
	}
	getSubsets(A, start + 1, currSubset, allSubsets);
	currSubset.push_back(A[start]);
	getSubsets(A, start + 1, currSubset, allSubsets);
	currSubset.pop_back();
}
vector<vector<int>> subsets(vector<int> &A) {
	vector<vector<int>> allSubsets;
	vector<int> currSubset;
    getSubsets(A, 0, currSubset, allSubsets);
	return allSubsets;
}
int maxSumSubsequence(vector<int> &arr) {
    int n = arr.size();
	int maximum = 0;
	vector<vector<int>> allSubsets = subsets(arr);
	for(auto x: allSubsets) {
		if(!x.empty() && is_sorted(x.begin(), x.end())) {
			maximum = max(maximum, accumulate(x.begin(), x.end(), 0));
		}
	}
	return maximum;
}

Java

class Solution {
	void getSubsets(int[] A, int start, List<Integer> currSubset, List<List<Integer>> allSubsets) {
		if (start == A.length) {
			allSubsets.add(new ArrayList(currSubset));
			return;
		}
		getSubsets(A, start + 1, currSubset, allSubsets);
		currSubset.add(A[start]);
		getSubsets(A, start + 1, currSubset, allSubsets);
		currSubset.remove(currSubset.size() - 1);
	}
	List<List<Integer>> subsets(int[] A) {
		List<List<Integer>> allSubsets = new ArrayList<>();
		List<Integer> currSubset = new ArrayList<>();
		getSubsets(A, 0, currSubset, allSubsets);
		return allSubsets;
	}
	int maxSumSubsequence(int[] arr) {
	    List<List<Integer>> allSubsets = subsets(arr);
		int maximum = 0;
		if(arr.length == 1) {
			return arr[0];
		}
		for(List<Integer> subset: allSubsets) {
			boolean valid = true;
			int sum = 0;
			for(int i = 0; i < subset.size() - 1; i++) {
				if(subset.get(i) >= subset.get(i + 1)) {
					valid = false;
					break;
				}
				sum += subset.get(i);
				if(i == subset.size() - 2) {
					sum += subset.get(i + 1);
				}
			}
			if(valid) {
				maximum = Math.max(maximum, sum);
			}
		}
		return maximum;
	}
}

Optimal Approach

In the optimal approach, we approach this problem as a variant of the Longest Increasing Subsequence problem, where instead of maximum the “length” parameter, we maximize the sum of the subsequence. The dp[i] state represents the maximum sum of the longest increasing subsequence which ends at position i. We traverse on all the elements from [0, i - 1] and try to form the longest increasing subsequence with maximum sum from these elements.

Analysis

• Time Complexity: O(n²)
• Space Complexity: O(n)

Implementation

C++

int maxSumSubsequence(vector<int> &arr) {
    int n = arr.size();
	vector<int> dp = arr;
	for(int i = 1; i < n; i++) {
		for(int j = 0; j < i; j++) {
			if(arr[i] >= arr[j]) {
				dp[i] = max(dp[j] + arr[i], dp[i]);
			}
		}
	}
	return *max_element(dp.begin(), dp.end());
}

Java

class Solution {
	int maxSumSubsequence(int[] arr) {
	    int n = arr.length;
		int dp[] = new int[n];
		for(int i = 0; i < n; i++) {
			dp[i] = arr[i];
		}
		for(int i = 1; i < n; i++) {
			for(int j = 0; j < i; j++) {
				if(arr[i] >= arr[j]) {
					dp[i] = Math.max(dp[j] + arr[i], dp[i]);
				}
			}
		}
		int maximum = 0;
		for(int i = 0; i < n; i++) {
			maximum = Math.max(maximum, dp[i]);
		}
		return maximum;
	}
}