Maximum Sum of 3 Non-Overlapping Subarrays LeetCode solution in Java

1
class Solution {
2
  public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
3
    int n = nums.length;
4
    int[] ans = new int[3];
5
    int[] pre = new int[n];
6
    int[] third = new int[n];
7
    for (int i = 0; i < n; ++i) { // prefix sum
8
      pre[i] = i == 0 ? nums[i] : nums[i] + pre[i - 1];
9
    }
10
    for (int i = n - k, max = 0; i >= 2 * k; --i) { // find the best index for the last part
11
      int cur = pre[i + k - 1] - pre[i - 1];
12
      max = Math.max(max, cur);
13
      third[i] = cur == max ? i : third[i + 1];
14
    }
15
    for (int i = k, first = 0, fmax = 0, max = 0; i + 2 * k - 1 < n; i++) {
16
      int cur = pre[i - 1] - (i == k ? 0 : pre[i - 1 - k]);
17
      if (cur > fmax) { // compute the best index for the first part on the fly
18
        fmax = cur;
19
        first = i - k;
20
      }
21
      int a = fmax; // first
22
      int b = pre[i + k - 1] - pre[i - 1]; // middle
23
      int c = pre[third[i + k] + k - 1] - pre[third[i + k] - 1]; // last
24
      if (a + b + c > max) {
25
        max = a + b + c;
26
        ans[0] = first;
27
        ans[1] = i;
28
        ans[2] = third[i + k];
29
      }
30
    }
31
    return ans;
32
  }
33
}