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.
1function maxSumOfThreeSubarrays(nums, k) {
2 const n = nums.length;
3 const prefix = new Array(n + 1).fill(0);
4 const left = new Array(n).fill(0);
5 const right = new Array(n).fill(n - k);
6
7 for (let i = 0; i < n; i++) {
8 prefix[i + 1] = prefix[i] + nums[i];
9 }
10
11 for (let i = k, total = prefix[k] - prefix[0]; i < n; i++) {
12 if (prefix[i + 1] - prefix[i + 1 - k] > total) {
13 total = prefix[i + 1] - prefix[i + 1 - k];
14 left[i] = i + 1 - k;
15 } else {
16 left[i] = left[i - 1];
17 }
18 }
19
20 for (let i = n - k - 1, total = prefix[n] - prefix[n - k]; i >= 0; i--) {
21 if (prefix[i + k] - prefix[i] >= total) {
22 total = prefix[i + k] - prefix[i];
23 right[i] = i;
24 } else {
25 right[i] = right[i + 1];
26 }
27 }
28
29 let maxSum = 0;
30 const result = [0, 0, 0];
31 for (let i = k; i <= n - 2 * k; ++i) {
32 let l = left[i - 1];
33 let r = right[i + k];
34 let totalSum = (prefix[i + k] - prefix[i]) + (prefix[l + k] - prefix[l]) + (prefix[r + k] - prefix[r]);
35 if (totalSum > maxSum) {
36 maxSum = totalSum;
37 result[0] = l;
38 result[1] = i;
39 result[2] = r;
40 }
41 }
42 return result;
43}
44
45// Example usage
46const nums = [1, 2, 1, 2, 6, 7, 5, 1];
47const k = 2;
48console.log(maxSumOfThreeSubarrays(nums, k));In JavaScript, this solution uses additional storage to maintain prefix sums and utilizes arrays left and right to store starting indices for optimized subarray sums. This strategic approach efficiently identifies the subarrays by calculating potential total sums.
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
The Python solution employs dynamic programming principles with additional vectors to optimize calculation of subarray sums. The left and right arrays capture optimal prefix values dynamically during algorithm execution to achieve the best subarray combinations.