LC 0689 [H] Maximum Sum of 3 Non Overlapping Subarrays - ALawliet/algorithms GitHub Wiki
(the last solution is best and easiest)
https://www.youtube.com/watch?v=sSjz_Cf4Bkw&t=327s&ab_channel=HappyCoding
how to find the max of 1 subarray? => sliding window
how to find the max of 2 subarray? => max of 1 subarray + value of 2 subarray > max of 2 subarray
so take 1 subarray, then build it it to 2, then to 3.
for each, keep the best indexes, the max total sums for each set of consecutive windows, and the current sum for that one window
hardest part is getting the indexes straight
class Solution:
def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:
bestOneIndex = 0
bestTwoIndex = [0, k]
bestThreeIndex = [0, k, k*2]
maxOneTotalSum = sum(nums[:k])
maxTwoTotalSum = sum(nums[:k*2])
maxThreeTotalSum = sum(nums[:k*3])
curOneSum = sum(nums[:k])
curTwoSum = sum(nums[k:k*2])
curThreeSum = sum(nums[k*2:k*3])
n = len(nums)
for i in range(1, n-k*3+1):
curOneSum = curOneSum - nums[i-1] + nums[i+k-1]
curTwoSum = curTwoSum - nums[i+k-1] + nums[i+k*2-1]
curThreeSum = curThreeSum - nums[i+k*2-1] + nums[i+k*3-1]
if curOneSum > maxOneTotalSum:
bestOneIndex = i
maxOneTotalSum = curOneSum
if curTwoSum + maxOneTotalSum > maxTwoTotalSum:
bestTwoIndex = [bestOneIndex, i+k]
maxTwoTotalSum = curTwoSum + maxOneTotalSum
if curThreeSum + maxTwoTotalSum > maxThreeTotalSum:
bestThreeIndex = bestTwoIndex + [i+k*2]
maxThreeTotalSum = curThreeSum + maxTwoTotalSum
return bestThreeIndex
'''
0 1 2 3 4 5 6 7
[1,2,1,2,6,7,5,1], 2
[3] [8] [12]
max sum => indexes of that window
max_of_1, loc_of_1 = 3, [0]
max_of_2, loc_of_2 = 11, [0,3]
max_of_3, loc_of_3 = 23, [0,3,5]
'''
Given an integer array nums and an integer k, find three non-overlapping subarrays of length k with maximum sum and return them.
https://www.youtube.com/watch?v=r_uJ9Vlqaqs
1. precompute fast sum lookups
2. store max of 1, 2, 3 sums to their windows and update
class Solution:
def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:
m = 3 # num windows
# precompute fast sum lookups
window_sums = [sum(nums[:k])]
for i in range(1, len(nums) - k + 1):
left = nums[i-1]
right = nums[i+k-1]
window_sums.append(window_sums[-1] - left + right)
# max_of_i = max(max_of_i, sum_current_subarray_i+max_of_[i-1])
# hashmap for max of up to m windows
max_sums = defaultdict(lambda: [0, []])
for a in range(0, len(nums) - k*m + 1): # max_of_1
for b in range(1, m+1): # max_of_2
# a is in the index of the 1st window, + k to get the index of next 2nd window that doesn't overlap
c = a + (b-1)*k # max_of_3, next window index to update with
update = window_sums[c] + max_sums[b-1][0] # sum_current_subarray_i+max_of_[b-1]
if update > max_sums[b][0]:
max_sums[b][0] = update
max_sums[b][1] = max_sums[b-1][1] + [c]
return max_sums[m][1] # loc_of_3
max_sum1, max_sum_of_1_to_2, max_sum_of_1_to_3,
I guess mw is Max Window sum.
3 pointer greedy
time: O(n)
space: O(k) fixed array of length k = O(1)
class Solution(object):
def maxSumOfThreeSubarrays(self,nums, k):
w1, w2, w3 = sum(nums[:k]), sum(nums[k:2*k]), sum(nums[2*k:3*k])
mw1, mw2, mw3 = w1, w1+w2, w1+w2+w3
mw1index, mw2index, mw3index = [0], [0,k], [0,k,2*k] #mw1,mw2,mw3's index.
for i in range(1, len(nums) - 3*k + 1): #last index for w1 window will be n-3k
w1 += nums[i-1 + k] - nums[i-1]
w2 += nums[i-1 + 2*k] - nums[i-1 + k]
w3 += nums[i-1 + 3*k] - nums[i-1 + 2*k]
if w1 > mw1:
mw1, mw1index = w1, [i] # [i]
if mw1+w2 > mw2:
mw2, mw2index = mw1+w2, mw1index+[i+k] # [i,i+k]
if mw2+w3 > mw3:
mw3, mw3index = mw2+w3, mw2index+[i+2*k] #[i,i+k,i+2*k]
return mw3index