Maximum Sum Increasing Subsequence

Given an array of n positive integers, find the maximum sum of an increasing subsequence. A subsequence is a sequence derived from the array that maintains the relative order of elements, and an increasing subsequence means the elements are in increasing order.

Input/Output Examples

plaintext
Example 1:
Input: arr = [1, 101, 2, 3, 100, 4, 5]
Output: 106
Explanation: The maximum sum increasing subsequence is [1, 2, 3, 100] with a sum of 106.

Example 2:
Input: arr = [3, 4, 5, 10]
Output: 22
Explanation: The entire array is an increasing subsequence with a sum of 22.

Example 3:
Input: arr = [10, 5, 4, 3]
Output: 10
Explanation: The maximum sum increasing subsequence is [10], since all other elements are smaller than 10.

Approach to find the Maximum Sum increasing subsequence

  1. Dynamic Programming Approach:
    • Use a 1D DP array dp[i] where dp[i] represents the maximum sum of an increasing subsequence ending at index **i**.
    • Initialize the DP array with the values of the array itself, i.e., dp[i] = arr[i], because the subsequence consisting of just one element is the element itself.
    • For each element arr[i], check all previous elements arr[j] (where j < i). If arr[i] > arr[j], update dp[i] = max(dp[i], dp[j] + arr[i]) to include arr[i] in the subsequence ending at j.
  2. Algorithm:
    • Initialize a DP array where each element is initialized to the corresponding value in the array.
    • Traverse the array and for each element arr[i], check all previous elements arr[j] and update the DP array if arr[i] can extend the subsequence ending at arr[j].
    • The final answer will be the maximum value in the DP array.
  3. Edge Cases:
    • If the array has only one element, the maximum sum is the element itself.
    • If all elements are in descending order, the maximum sum will be the largest element in the array.

C++ Program to find the Maximum Sum increasing subsequence

cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Function to find the maximum sum increasing subsequence
int maxSumIncreasingSubsequence(vector<int>& arr) {
    int n = arr.size();
    vector<int> dp(arr); // Initialize dp with the values of arr

    // Build the DP array
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j]) {
                dp[i] = max(dp[i], dp[j] + arr[i]);
            }
        }
    }

    // Find the maximum value in dp
    return *max_element(dp.begin(), dp.end());
}

int main() {
    vector<int> arr = {1, 101, 2, 3, 100, 4, 5};
    int result = maxSumIncreasingSubsequence(arr);
    cout << "Maximum sum increasing subsequence: " << result << endl;
    
    return 0;
}

Java program to find the maximum sum increasing subsequence

java
import java.util.Arrays;

public class MaxSumIncreasingSubsequence {

    // Function to find the maximum sum increasing subsequence
    public static int maxSumIncreasingSubsequence(int[] arr) {
        int n = arr.length;
        int[] dp = Arrays.copyOf(arr, n); // Initialize dp with the values of arr

        // Build the DP array
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + arr[i]);
                }
            }
        }

        // Find the maximum value in dp
        int maxSum = dp[0];
        for (int i = 1; i < n; i++) {
            maxSum = Math.max(maxSum, dp[i]);
        }

        return maxSum;
    }

    public static void main(String[] args) {
        int[] arr = {1, 101, 2, 3, 100, 4, 5};
        int result = maxSumIncreasingSubsequence(arr);
        System.out.println("Maximum sum increasing subsequence: " + result);
    }
}

Python program to find the maximum sum increasing subsequence

python
# Function to find the maximum sum increasing subsequence
def max_sum_increasing_subsequence(arr):
    n = len(arr)
    dp = arr[:]  # Initialize dp with the values of arr

    # Build the DP array
    for i in range(1, n):
        for j in range(i):
            if arr[i] > arr[j]:
                dp[i] = max(dp[i], dp[j] + arr[i])

    # Find and return the maximum value in dp
    return max(dp)

# Example usage
if __name__ == "__main__":
    arr = [1, 101, 2, 3, 100, 4, 5]
    result = max_sum_increasing_subsequence(arr)
    print("Maximum sum increasing subsequence:", result)

Time Complexity:

  • O(n²): We use two nested loops to traverse the array. The outer loop runs for n elements, and the inner loop runs for all elements before the current element, making the time complexity quadratic.

Space Complexity:

  • O(n): We use an additional DP array of size n to store the maximum sum of increasing subsequences ending at each index.

DSA

1721

886

Related Articles