The Maximum Sum Increasing Subsequence Problem.

Sometimes, the stars in your life align and ~~force~~ strongly suggest you to write a new article. That happened to me recently when somebody mentioned that I do not often write about software engineering. Shortly after that, I was tasked with solving the problem in the title. Since I rarely publish or write about my code, I took it as a hint from the universe to change that. All three of you readers that will find this as fascinating as I do, get ready to geek out over the maximum sum increasing subsequence problem.

The Problem.

Let's present the task first.

Given an array of n positive integers, find the sum of maximum sum subsequence of the given array such that the integers in the subsequence are sorted in increasing order.

To illustrate the example, for the array [1, 101, 2, 3, 100, 4, 5], the solution are numbers [2, 3, 100] giving us sum 105. You can find the original problem here.

Can't Make It Too Easy.

Of course, I don't want to do the standard exercise, so let's add a few more options.

The first change will be that we might want to include zero or negative numbers in the input array. We will be able to choose whether our output contains only positive integers, positive integers and zero, any integers, or any integers except zero.

The second change will be that we might remove the whole increasing sequence requirement and simply look for the maximum sum subsequence.

The third change is a little formatting addition. If our output starts with zero, we might want to exclude the leading zero.

The last change deals with conflicts. If there are two or more matches with equal sums, we should be able to specify if we want to return the first or the last match.

The Solution.

One additional constraint I wanted to add was to use a single loop on the input. Before we talk about the solution, please have a look at the code on Github. Don't worry if it takes you a while to understand! It took me even longer to arrive at the final solution.

Main Concepts.

To fully understand the solution, I need to explain a few concepts first. As I mentioned, we will loop through the input only once. That means we cannot come back to compare our potential result with any previous values.

Admittedly, I added most of the constraints after I wrote the initial solution. The takeaway here is to solve for one use case first, iterate, refactor, and add more use cases later. Otherwise, it's easy to get stuck when presented with a complex task like this one.

Notice the series initial state. We start with the lowest value possible since we are looking for the largest sum. If we wanted to find the lowest sum, we'd start with infinity.

The meat of the program is in the getMaxSeries() method. There is the single loop through all input numbers. We pass an array with two entries as the initial value. One entry is used to store the final output, the other entry is for temporary computations. We perform two operations for every input value. First, we update the temporary result. Then, we update the final output.

Notice that most methods accept the same parameters. That makes it super easy to extend this program with more methods. We pass the current input number first, then the temporary result, then the options object, and the current input number index last.

Key Insights.

Apart from the main concepts above, two key insights helped me arrive at this solution.

The concept of a net positive value. Adding net positive value to series won't decrease its sum. For example, adding any positive integer or zero to series guarantees the sum won't decrease. A negative integer can be a net positive value, too, when it's higher than the existing sum.
The concept of a net negative series. Derived from the net positive value concept, you can think of a net negative series as worthless series. They can potentially be directly replaced with net positive values. Such series include series in the initial state and series with negative sum.

Immutability Rocks!

You might have noticed that a lot of the solution contains immutable references. That's a personal preference as I think it makes it very clear when we modify variable values.

Additionally, thanks to that, we end up using only a single if statement. And look at that beauty inside the getMaxSeries() method. We can clearly see we define two operations mentioned above and then receive two results after applying each one of them.

Note: In practice, you'd probably use a library for this or move these helpers inside a separate file.

Series Operations.

Let's talk about the getSeriesOperation() function first since it gets run first. The returned operation can be one of the following three.

We return the initial state when we decide to discard the current number. For example, we could discard negative integers if the requirements disallow them. The isValueIgnored() method should be self-explanatory if you know JavaScript.
We forget about the current temporary result and replace it with the current number. We might want to do this if the current sum is say -10 and the current number is 10. There is no point in doing anything else as adding these two numbers together would produce 0, while keeping only the current number would produce a sum of 10.
We add the current number to the temporary result. This one should be obvious. We want to keep adding numbers to the series as long as they match our requirement conditions.

Getting the Output.

The last part of our program is the updateOutputSeries() function. It decides whether to keep the previous output value or replace it with the current temporary result. We overwrite the output only if the corresponding condition is met. It differs slightly depending on which sequence match we want to return.

Conclusion.

And that's it! I am not sure if it's obvious from the solution, but it's smart enough to handle even some tricky cases. Imagine we have an input like [10, -100, 10, -8, -1, 20]. Perhaps you would think that the result is [20], but that would be wrong. The first 10 is correctly not in the result because -100 would turn [10, -100] into a net negative series. However, the second 10 should be in the result because [10, -8, -1] won't be a net negative series! Hence, the correct answer is [10, -8, -1, 20] which gives us sum 21. Handling such examples is my favourite feature of this solution, right next to the API extendability.

I think that would be enough geeking out for today, I hope you enjoyed the article!

Thank you for reading.

This article also appeared on DEV.