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?