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.
The Java solution uses a prefix sum array to quickly compute subarray sums. To identify the optimal subarrays, it employs two sliding window techniques (left and right) to track ideal starting indices for the leftmost and rightmost subarrays. The main loop determines the middle subarray and calculates the total possible sum.
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.
1function maxSumOfThreeSubarraysDP(nums, k) {
2 const n = nums.length;
3 const prefix = new Array(n + 1).fill(0);
4 const dp = new Array(n).fill(0);
5 const left = new Array(n).fill(0);
6 const right = new Array(n).fill(n - k);
7
8 for (let i = 0; i < n; i++) {
9 prefix[i + 1] = prefix[i] + nums[i];
10 }
11
12 for (let i = k; i < n; i++) {
13 if (prefix[i + 1] - prefix[i + 1 - k] > dp[i - 1]) {
14 dp[i] = prefix[i + 1] - prefix[i + 1 - k];
15 left[i] = i + 1 - k;
16 } else {
17 dp[i] = dp[i - 1];
18 left[i] = left[i - 1];
19 }
20 }
21
22 right[n - k] = n - k;
23 for (let i = n - k - 1; i >= 0; i--) {
24 if (prefix[i + k] - prefix[i] >= prefix[right[i + 1] + k] - prefix[right[i + 1]]) {
25 right[i] = i;
26 } else {
27 right[i] = right[i + 1];
28 }
29 }
30
31 let maxSum = 0;
32 const result = [0, 0, 0];
33 for (let i = k; i <= n - 2 * k; ++i) {
34 let l = left[i - 1];
35 let r = right[i + k];
36 let totalSum = (prefix[i + k] - prefix[i]) + (prefix[l + k] - prefix[l]) + (prefix[r + k] - prefix[r]);
37 if (totalSum > maxSum) {
38 maxSum = totalSum;
39 result[0] = l;
40 result[1] = i;
41 result[2] = r;
42 }
43 }
44 return result;
45}
46
47// Example usage
48const nums = [1, 2, 1, 2, 6, 7, 5, 1];
49k = 2;
50console.log(maxSumOfThreeSubarraysDP(nums, k));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.
Solve with full IDE support and test cases