Leetcode 689. Maximum Sum of 3 Non-Overlapping Subarrays (I)

January 23, 2018

Introduction

I came cross the algorithm this evening while I attended word press meeting in Vancouver down town Microsoft office. I started to think about the algorithm. I like to write down how I analyze the algorithm systematically, look like an engineer.

The algorithm link is here in Chinese.

Step by step

Thinking process is more important for me right now. I know that I have improved a lot how to write clean code, readable code through last 8 months mock interview practices.

Let the journey begin, how to approach a problem like an engineer.

First of all, let me write down the constraints:

Integer array, given K value, find 3 subarray, non-overlap, the sum is maximum.

What is the time complexity for the algorithm? linear, or n², or higher time complexity? Can we solve the problem using linear time?

Of course, brute force solution takes O(n³) time. Just try to find 3 start index by enumerate the index value from 1 to length - 1.

How to approach the problem?

If it is neither in mock interview nor in phone screen. Let us work on the very basics and take time. I did take more than 30 minutes to think and write down the notes. 

Non-overlap constraint

If constraints non-overlapping is not required, so the problem is very easy, just use O(N) time where N is the array’s length to get the top three sum of subarray by linear scan the array from left to right.

Each iteration only one addition one subtraction and apply dynamic programming techniques.

K = 2, the array size is 100

What if we work on this task, K = 2, array size is 100. How do we find those three subarrays with maximum sum?

Preprocess the array using O(N) time

We can easily preprocess the array to get any index with its maximum sum from i = 0 to current index – 1, each index with size K subarray. It is processed by scanning left to right using Dynamic programming and time complexity O(N).

Likewise, we can preprocess the array to get any index with it maximum sum from i > currentIndex to length -1. It is processed by scanning  the array from right to left using dynamic programming and time complexity O(N).

How to find 3 subarray with top 3 sum?

It is not good idea, since first those top 3 sum may be overlapped, and then we can prove that top 3 sum may end up biggest sum of 3 subarray. In theory, it is not true.

Left, middle, right 3 subarray

Let us think about the order of search, how many options? Start first, and then search rest two; start last, and then search first two; or start from middle one, and then search left and right both sides.

Find left subarray first

Brute force first one for its start position, and then we will work on the subproblem to find two subarrays to get maximum sum. The subproblem to find two subarrays is with time complexity O(N).  The whole solution will be O(N²).

Find middle subarray first

Advice for Julia 

It is good idea to write something down for my favorite hard level algorithm. Maybe I also should write down something to make it more pleasant later on to review.

Like the mistake I make in the first 30 minutes thinking process. On January 22, 2018, my mistake is to mix the algorithm with the problem "Find top kth sum of subarrays in the array". The algorithm I tried to solve is much more complicated and then I thought about more than ten minutes.


On Jan. 22, 2018, second mistake I made is not to enumerate all options for three subarrays.What I mean is that there are options, work on leftmost subarray first, or middle subarray first, or rightmost subarray first.

On Jan. 22, 2018, third mistake I did not realize I need to brute force one of subarrays. Ask myself why?

Brute force one of subarrays, and then try to find the rest using preprocessed result, looking up only takes O(1) time. Only work on the middle subarray first, and then left is maximum subarray, right is also maximum subarray.