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.
1#include <iostream>
2#include <vector>
3using namespace std;
4
5vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
6 int n = nums.size();
7 vector<int> prefix(n + 1, 0);
8 for (int i = 0; i < n; i++) {
9 prefix[i + 1] = prefix[i] + nums[i];
10 }
11 vector<int> left(n, 0), right(n, n - k);
12 for (int i = k, total = prefix[k] - prefix[0]; i < n; i++) {
13 if (prefix[i + 1] - prefix[i + 1 - k] > total) {
14 left[i] = i + 1 - k;
15 total = prefix[i + 1] - prefix[i + 1 - k];
16 } else {
17 left[i] = left[i - 1];
18 }
19 }
20 for (int i = n - k - 1, total = prefix[n] - prefix[n - k]; i >= 0; i--) {
21 if (prefix[i + k] - prefix[i] >= total) {
22 right[i] = i;
23 total = prefix[i + k] - prefix[i];
24 } else {
25 right[i] = right[i + 1];
26 }
27 }
28 vector<int> ans(3, 0);
29 int max_sum = 0;
30 for (int i = k; i <= n - 2 * k; ++i) {
31 int l = left[i - 1], r = right[i + k];
32 int current_sum = prefix[l + k] - prefix[l] + prefix[i + k] - prefix[i] + prefix[r + k] - prefix[r];
33 if (current_sum > max_sum) {
34 max_sum = current_sum;
35 ans = {l, i, r};
36 }
37 }
38 return ans;
39}
40
41int main() {
42 vector<int> nums = {1, 2, 1, 2, 6, 7, 5, 1};
43 int k = 2;
44 vector<int> result = maxSumOfThreeSubarrays(nums, k);
45 for (int i : result) {
46 cout << i << " ";
47 }
48 return 0;
49}The C++ solution implements the prefix sum strategy with two additional arrays (left, right) to efficiently calculate possible subarray sums. It iterates over each potential middle subarray to find the maximum total sum, using pre-calculated best subarrays from both sides.
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 the Java solution, a dynamic programming array (dp) is utilized to track subarray sums. The code ensures efficient recalculations and coordinated updating of left and right best subarray indicators. The final middle subarray selection considers all these elements to find optimal results.