Python - Maximum Sum Increasing Subsequence

Python – Maximum Sum Increasing Subsequence

The Maximum Sum Increasing Subsequence (MSIS) problem is a classic dynamic programming challenge. Given an array of integers, the objective is to find a subsequence (not necessarily contiguous) where the elements are in strictly increasing order and the sum of these elements is maximized.

Problem Statement

Given an array arr of size n, determine the maximum sum that can be obtained from an increasing subsequence. If the array is empty, the output should be 0.

Sample Input and Output

Example 1:

</>

Copy

# Input:
arr = [1, 101, 2, 3, 100, 4, 5]

# Explanation:
# The maximum sum increasing subsequence is [1, 2, 3, 100]
# Sum = 1 + 2 + 3 + 100 = 106

# Output:
106

Explanation: In this example, the subsequence [1, 2, 3, 100] is strictly increasing and gives the maximum possible sum of 106.

Example 2:

</>

Copy

# Input:
arr = [3, 4, 5, 10]

# Explanation:
# Since the entire array is already increasing,
# the maximum sum increasing subsequence is [3, 4, 5, 10]
# Sum = 3 + 4 + 5 + 10 = 22

# Output:
22

Explanation: The array [3, 4, 5, 10] is already in strictly increasing order. Therefore, the maximum sum is simply the sum of all its elements, which is 22.

Solution Approach

We use dynamic programming to solve the MSIS problem efficiently. Define a DP array dp where each element dp[i] represents the maximum sum of an increasing subsequence ending at index i. The recurrence relation is:

dp[i] = arr[i] + max(dp[j]) for all j such that 0 ≤ j < i and arr[j] < arr[i]

If no valid j exists (i.e., there is no smaller element before arr[i]), then dp[i] remains as arr[i]. The answer is the maximum value in the dp array after processing all elements.

Python Program

</>

Copy

def max_sum_increasing_subsequence(arr):
    """
    Compute the maximum sum of an increasing subsequence in the given array.
    
    Parameters:
    arr (list): List of integers.
    
    Returns:
    int: Maximum sum of any increasing subsequence.
    """
    if not arr:
        return 0
    n = len(arr)
    # Initialize dp array where each dp[i] starts as the value of arr[i]
    dp = arr.copy()
    
    # Build the dp array by checking all previous elements
    for i in range(1, n):
        for j in range(i):
            # If arr[j] is less than arr[i], we can append arr[i] to the subsequence ending at j
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j] + arr[i])
    
    # The result is the maximum value in the dp array
    return max(dp)
# Test examples
print("Example 1:")
arr1 = [1, 101, 2, 3, 100, 4, 5]
print("Input:", arr1)
print("Maximum Sum Increasing Subsequence:", max_sum_increasing_subsequence(arr1))  # Expected output: 106
print("\nExample 2:")
arr2 = [3, 4, 5, 10]
print("Input:", arr2)
print("Maximum Sum Increasing Subsequence:", max_sum_increasing_subsequence(arr2))  # Expected output: 22

Explanation: The function max_sum_increasing_subsequence initializes a DP array with the original array values. It then iterates over each element, and for each arr[i], it checks all previous elements arr[j] (where j < i). If arr[j] is smaller than arr[i], it updates dp[i] to be the maximum of its current value and dp[j] + arr[i]. Finally, the maximum value in the DP array represents the maximum sum of an increasing subsequence.

Conclusion

The Maximum Sum Increasing Subsequence problem demonstrates the power of dynamic programming by breaking down a complex problem into smaller, manageable subproblems. By maintaining a DP array that captures the maximum sum ending at each index, we can efficiently compute the overall maximum sum of any increasing subsequence. This approach is both intuitive and effective, making it a popular choice for technical interviews and algorithm challenges.

TutorialKart

Python – Maximum Sum Increasing Subsequence