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

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.

Brainstorm the ideas

Need to brainstorm the ideas. Write down a list of ideas to work on.

Overlap – constraint, how to handle it?

Need to find  3 * K distinct elements in the array, and also 3 subarrays in the array not overlap

3 subarrays, how about one subarray, two subarray, four subarrays

It seems like 2 sum, 3 sum, 4 sum, k sum problem.

How to find three sum of subarrays? Enumerate one of the subarray, and search other two with maximum sums.

Two subarrays
We can use O(N) time, we just enumerate all possible subarray for the first one with small start index, and then find maximum subarray on it right side.

One subarray
We can using O(1) time to solve it. Preprocess the array using O(N) time and also dynamic programming to get any index and its right side maximum subarray sum or left side maximum subarray sum.

How about thinking bottom up?
Work on 1 subarray, and then two subarrays, and then three subarrays? Instead of breaking down three subarrays to two subarrays to 1 subarray.

Top k sum of subarrays
Let us differentiate the problem with top three sum of subarrays or top k sum of subarrays problem. 

Try to avoid complicated math theory, we even cannot tell that top three sum of subarrays with non-overlapping can add to maximum sum of three subarrays. 

Preprocessing

Preprocess the array using dynamic programming, we can do the work using O(N) time. What is the common calculation we can do for the algorithm. 

What is the time complexity we can target to solve the problem?

What is most common problems on solving this problem? 

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.