wish_me's blog

Maximum Sum of 3 Non-Overlapping Subarrays
By wish_me, history, 7 years ago, In English

In a given array nums of positive integers, find three non-overlapping subarrays with maximum sum.

Each subarray will be of size k, and we want to maximize the sum of all 3*k entries.

Return the result as a list of indices representing the starting position of each interval (0-indexed). If there are multiple answers, return the lexicographically smallest one.

Example:

Input: [1,2,1,2,6,7,5,1], 2

Output: [0, 3, 5]

Explanation: Subarrays [1, 2], [2, 6], [7, 5] correspond to the starting indices [0, 3, 5].

We could have also taken [2, 1], but an answer of [1, 3, 5] would be lexicographically larger.

Note:

nums.length will be between 1 and 20000.

nums[i] will be between 1 and 65535.

k will be between 1 and floor(nums.length / 3).

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Firstly, for every position of the array i such that 0 ≤ i and i + k < n we calculate the sum arr[i] + arr[i + 1] + ... + arr[i + k - 1] and store it in sum[i].

Then we start iterating the sum array from k'th index to n - 2k'th index and we assume that it is the middle segment of the 3 segments. Now all we have to do is to find the maximum sum from the range sum[0], ..., sum[i - k](this will be the first segment) and maximum sum from the range sum[i + k], ...sum[n - k](this is the 3rd segment). But these are all prefix and suffixes of the sum array. So we can pre-calculate the maximum sums in the prefix and suffix and use them here. Finally we just take the maximum from all of the total sums we found. Now the problem asks about the indexes. So we just keep track of the index in our calculation.

Overall complexity: O(n)

→ Reply