Sponsored
Sponsored
This approach uses a prefix sum array to quickly calculate the sum of any subarray and a sliding window technique to explore possible starting points for the subarrays.
Time Complexity: O(n), since we make a constant number of passes through the array.
Space Complexity: O(n), due to the prefix, left, and right arrays.
1def maxSumOfThreeSubarrays(nums, k):
2 n = len(nums)
3 prefix = [0] * (n + 1)
4 for i in range(1, n + 1):
5 prefix[i] = prefix[i - 1] + nums[i - 1]
6 left = [0] * n
7 right = [0] * n
8 for i in range(k, n):
9 if prefix[i + 1] - prefix[i + 1 - k] > prefix[left[i - 1] + k] - prefix[left[i - 1]]:
10 left[i] = i + 1 - k
11 else:
12 left[i] = left[i - 1]
13 for i in range(n - k - 1, -1, -1):
14 if prefix[i + k] - prefix[i] >= prefix[right[i + 1] + k] - prefix[right[i + 1]]:
15 right[i] = i
16 else:
17 right[i] = right[i + 1]
18 max_sum = 0
19 ans = [-1, -1, -1]
20 for mid in range(k, n - 2 * k + 1):
21 l, r = left[mid - 1], right[mid + k]
22 total_sum = (prefix[l + k] - prefix[l]) + (prefix[mid + k] - prefix[mid]) + (prefix[r + k] - prefix[r])
23 if total_sum > max_sum:
24 max_sum = total_sum
25 ans = [l, mid, r]
26 return ans
27
28# Example usage
29nums = [1, 2, 1, 2, 6, 7, 5, 1]
30k = 2
31print(maxSumOfThreeSubarrays(nums, k))This Python solution computes prefix sums to simplify subarray calculations. It keeps track of the best possible subarray starting indices for the left and right subarrays. The middle subarray iterates to check for the highest achievable sum combining left, middle, and right subarrays. The process carefully maintains indices for lexicographical order.
This approach employs dynamic programming alongside a sliding window to optimize subarray sum calculations and ensure non-overlapping conditions.
Time Complexity: O(n), for traversal of the nums array multiple times.
Space Complexity: O(n), utilizing the dp, prefix, left, and right arrays.
1
In JavaScript, this solution integrates dynamic programming to enhance efficiency when juxtaposing subarray sums. By aligning calculations with pre-computed values (left, right), it offers a reliable path to identify larger results within allowed configurations.