Definition
- Sum objective – instead of counting elements (LIS), sum their values to find the heaviest rising subsequence.
- Seed – each dp[i] starts as the element's own value, because a single element is a valid rising subsequence.
- Extension – for each i, look back at every j < i where a[j] < a[i] and set dp[i] = max(dp[i], dp[j] + a[i]).
- Global answer – the answer is the maximum dp[i] across all indices, because the best subsequence can end anywhere.
- O(n^2) time – the nested loop checks every earlier index for each position.
The National Bank of India looks at a customer's series of deposit amounts and finds the strictly rising subsequence of deposits whose total amount is the largest. The bank rewards customers whose deposits show growing discipline, and the prize goes to the sequence with the biggest sum.
Understanding the Concepts
What is the Maximum Sum Increasing Subsequence?
Given an array of numbers, find the maximum sum of any strictly increasing subsequence. A subsequence keeps relative order but need not be contiguous, and it must be strictly increasing (each element is strictly greater than the previous). This adapts the Longest Increasing Subsequence DP to optimize total value instead of count.
package com.bank.rewards;
public class MaxSumIncreasingSubseq {
public static int maxSumIS(int[] deposits) {
int n = deposits.length;
if (n == 0) return 0;
int[] dp = deposits.clone(); // seed each with its own value
int best = dp[0];
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (deposits[j] < deposits[i]) {
dp[i] = Math.max(dp[i], dp[j] + deposits[i]);
}
}
best = Math.max(best, dp[i]);
}
return best;
}
}
Why seed each index with the element's own value?
A single element by itself is a valid strictly increasing subsequence of length 1. Its sum is just the element's value. So dp[i] starts as deposits[i], meaning the best increasing subsequence ending at i is at least the element alone. Extensions from earlier elements can only improve this.
package com.bank.rewards;
public class SeedingDemo {
public static void trace() {
int[] deposits = {4, 1, 3, 7};
// Initial dp (seeded): [4, 1, 3, 7]
// dp[0]=4: no earlier elements
// dp[1]=1: deposits[0]=4 > 1, so no extension
// dp[2]=3: deposits[1]=1 < 3, dp[2]=max(3, 1+3)=4
// deposits[0]=4 > 3, skip
// dp[3]=7: deposits[0]=4 < 7, dp[3]=max(7, 4+7)=11
// deposits[1]=1 < 7, dp[3]=max(11, 1+7)=11
// deposits[2]=3 < 7, dp[3]=max(11, 4+7)=11
// Best = max(4, 1, 4, 11) = 11
// Subsequence: [4, 7] with sum 11
System.out.println("Max sum: " + MaxSumIncreasingSubseq.maxSumIS(deposits));
}
}
Max sum: 11
How does the extension work?
For each index i, you look back at every earlier index j. If deposits[j] < deposits[i], the increasing subsequence ending at j can be extended by deposits[i]. The new sum would be dp[j] + deposits[i]. You take the maximum over all such extensions and the seed value.
// Extension logic:
// For i=3 (value 7):
// j=0 (value 4): 4 < 7 → candidate = dp[0] + 7 = 4 + 7 = 11
// j=1 (value 1): 1 < 7 → candidate = dp[1] + 7 = 1 + 7 = 8
// j=2 (value 3): 3 < 7 → candidate = dp[2] + 7 = 4 + 7 = 11
// dp[3] = max(7, 11, 8, 11) = 11
How is this different from Longest Increasing Subsequence?
LIS counts elements and uses dp[i] = max(dp[i], dp[j] + 1). MSIS sums values and uses dp[i] = max(dp[i], dp[j] + a[i]). The structure is identical: look back at every smaller element and extend. The value objective prevents the O(n log n) patience sorting / tails-array speedup because the optimal sum ending at each value does not form a monotonic structure.
// LIS: dp[i] = max(dp[j] + 1) for j<i with a[j]<a[i], seeded with 1
// MSIS: dp[i] = max(dp[j] + a[i]) for j<i with a[j]<a[i], seeded with a[i]
// LIS can be O(n log n) with tails array
// MSIS stays O(n^2) because sum objective breaks the tails trick
What is the time and space complexity?
| Approach | Time | Space | Notes |
|---|---|---|---|
| Nested loop DP | O(n^2) | O(n) | Standard approach |
| Brute force (all subsequences) | O(2^n) | O(n) | Exponential |
The O(n^2) approach is the best known for this problem because the sum objective prevents the binary-search optimization that speeds up LIS.
What are edge cases?
Edge cases include an empty array (return 0), a single element (return that element), a strictly decreasing array (the best is the single largest element), and all elements being equal (the best is any single element).
package com.bank.rewards;
public class EdgeCases {
public static void test() {
System.out.println(MaxSumIncreasingSubseq.maxSumIS(new int[]{})); // 0
System.out.println(MaxSumIncreasingSubseq.maxSumIS(new int[]{5})); // 5
System.out.println(MaxSumIncreasingSubseq.maxSumIS(new int[]{5, 3, 1})); // 5
System.out.println(MaxSumIncreasingSubseq.maxSumIS(new int[]{4, 4, 4})); // 4
}
}
0
5
5
4
What are common mistakes?
The most common mistake is seeding dp with 0 instead of the element's value. This misses the case where the element alone is the best subsequence. Another mistake is using >= instead of > for the strictly increasing check.
package com.bank.rewards;
public class CommonMistakes {
// WRONG: seed dp with 0
// dp[i] = 0 means the element alone has sum 0, not its value!
// Fix: dp = deposits.clone()
// WRONG: using >= instead of > (allows equal values)
// This produces a non-decreasing subsequence, not strictly increasing
// Fix: use deposits[j] < deposits[i] (strictly less)
}
How do you recover the actual subsequence?
Maintain a parent array where parent[i] records the index j that gave the best extension for i. After finding the best ending index, trace back through the parent array to reconstruct the subsequence.
package com.bank.rewards;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class RecoverSubsequence {
public static List<Integer> recoverMSIS(int[] deposits) {
int n = deposits.length;
int[] dp = deposits.clone();
int[] parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = -1;
int bestIdx = 0;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (deposits[j] < deposits[i] && dp[j] + deposits[i] > dp[i]) {
dp[i] = dp[j] + deposits[i];
parent[i] = j;
}
}
if (dp[i] > dp[bestIdx]) bestIdx = i;
}
List<Integer> result = new ArrayList<>();
for (int idx = bestIdx; idx != -1; idx = parent[idx]) {
result.add(deposits[idx]);
}
Collections.reverse(result);
return result;
}
public static void main(String[] args) {
System.out.println(recoverMSIS(new int[]{4, 1, 3, 7})); // [4, 7]
}
}
[4, 7]
How is this used in banking?
At the National Bank of India, the rewards team examines a customer's series of deposit amounts and finds the strictly rising subsequence whose total is the largest. Customers with a high maximum-sum increasing subsequence are considered to have strong growing deposit discipline and receive bonus interest.
package com.bank.rewards;
public class DepositRewards {
public static void main(String[] args) {
int[] deposits = {500, 200, 300, 700, 100, 800};
int maxSum = MaxSumIncreasingSubseq.maxSumIS(deposits);
System.out.println("Best rising deposit total: " + maxSum);
// Rising subsequence: [200, 300, 700, 800] = 2000
// Or: [500, 700, 800] = 2000
}
}
Best rising deposit total: 2000
Visual Overview
DP Table Fill ============== Deposits: [4, 1, 3, 7] Seed dp: [4, 1, 3, 7] i=1 (val 1): j=0: 4 < 1? No → skip dp: [4, 1, 3, 7] i=2 (val 3): j=0: 4 < 3? No → skip j=1: 1 < 3? Yes → dp[2] = max(3, 1+3) = 4 dp: [4, 1, 4, 7] i=3 (val 7): j=0: 4 < 7? Yes → dp[3] = max(7, 4+7) = 11 j=1: 1 < 7? Yes → dp[3] = max(11, 1+7) = 11 j=2: 3 < 7? Yes → dp[3] = max(11, 4+7) = 11 dp: [4, 1, 4, 11] Answer: max(4, 1, 4, 11) = 11 Subsequence: [4, 7] LIS vs MSIS Comparison ======================= ┌──────────────────────┬───────────────────────┐ │ LIS (count) │ MSIS (sum) │ ├──────────────────────┼───────────────────────┤ │ Seed: dp[i] = 1 │ Seed: dp[i] = a[i] │ │ Extend: dp[j] + 1 │ Extend: dp[j] + a[i] │ │ Tails: O(n log n) │ No tails: O(n^2) │ │ Objective: length │ Objective: value sum │ └──────────────────────┴───────────────────────┘
Key Takeaway
The Maximum Sum Increasing Subsequence adapts the Longest Increasing Subsequence DP by swapping the objective from counting elements to summing values. For each index you compute the maximum sum of a strictly increasing subsequence ending at that element, seeded with the element's own value because a single element is a valid subsequence on its own.
To extend, you look back at every earlier index holding a strictly smaller value. The increasing subsequence ending there can be continued by the current element, so the new sum is dp[j] + a[i]. You take the maximum over all such extensions. The global answer is the maximum dp[i] across all indices because the best subsequence can end anywhere.
At the National Bank of India, the rewards team examined a customer's deposit history and found the strictly rising subsequence with the largest total, rewarding customers whose deposits showed strong growing discipline. The nested-loop DP computed the answer in O(n^2) time.
The senior-level insight is that the value objective prevents the O(n log n) tails-array speedup that works for LIS. The tails trick relies on a monotonic relationship between subsequence length and the smallest ending value, which breaks when the objective is sum instead of count. This is why MSIS stays at O(n^2).
Remember one sentence: seed each index with its own value, extend from the best earlier smaller sum, and the global maximum is the answer.
---