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.
1using System;
2
3public class Solution {
4 public int[] MaxSumOfThreeSubarrays(int[] nums, int k) {
5 int n = nums.Length;
6 int[] prefix = new int[n + 1];
7 for (int i = 0; i < n; i++) {
8 prefix[i + 1] = prefix[i] + nums[i];
9 }
10 int[] left = new int[n];
11 int[] right = new int[n];
12 for (int i = k, total = prefix[k] - prefix[0]; i < n; i++) {
13 if (prefix[i + 1] - prefix[i + 1 - k] > total) {
14 total = prefix[i + 1] - prefix[i + 1 - k];
15 left[i] = 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 total = prefix[i + k] - prefix[i];
23 right[i] = i;
24 } else {
25 right[i] = right[i + 1];
26 }
27 }
28 int[] ans = new int[3];
29 int maxSum = 0;
30 for (int i = k; i <= n - 2 * k; ++i) {
31 int l = left[i - 1];
32 int r = right[i + k];
33 int currentSum = prefix[i + k] - prefix[i] + prefix[l + k] - prefix[l] + prefix[r + k] - prefix[r];
34 if (currentSum > maxSum) {
35 maxSum = currentSum;
36 ans[0] = l;
37 ans[1] = i;
38 ans[2] = r;
39 }
40 }
41 return ans;
42 }
43
44 public static void Main(string[] args) {
45 Solution solution = new Solution();
46 int[] nums = {1, 2, 1, 2, 6, 7, 5, 1};
47 int k = 2;
48 int[] result = solution.MaxSumOfThreeSubarrays(nums, k);
49 Console.WriteLine(string.Join(", ", result));
50 }
51}This C# solution combines prefix sums and sliding window principles to determine the maximum subarray sums for three non-overlapping sections within the input list. By maintaining correct indices for left and right subarrays, it efficiently finds the middle subarray to maximize the total 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.
1
This C solution introduces a dynamic programming table (dp) to record the maximum sum up to each point. Using left and right tracking, it determines the best left and right subarrays. A single pass checks for optimal middle subarrays using this dynamic information.