Maximum Sum of 3 Non-Overlapping Subarrays

/*
Refer to below link for details analysis.
https://leetcode.com/problems/maximum-sum-of-3-non-overlapping-subarrays/discuss/108231/C++Java-DP-with-explanation-O(n)/110501

Time Complexity = O(n)

Space Complexity = O(n)
*/
class Solution {
    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        if (nums == null || nums.length < 3 * k) {
            return new int[3];
        }
        if (nums.length == 3 * k) {
            return new int[]{0, k, 2 * k};
        }

        int n = nums.length;
        int[] sums = new int[n+1];
        int[] posRight = new int[n];
        int[] posLeft = new int[n];
        int[] result = new int[3];

        for (int i = 0; i < n; i++) {
            sums[i+1] = sums[i] + nums[i];
        }

        int lastSum = sums[k] - sums[0];
        for (int i = k + 1; i <= n - 2*k; i++) {
            int sum = sums[i] - sums[i-k];
            if (sum > lastSum) {
                posLeft[i] = i-k;
                lastSum = sum;
            } else {
                posLeft[i] = posLeft[i-1];
            }
        }

        lastSum = sums[n] - sums[n-k];
        posRight[n - 2*k] = n-k;
        for (int i = n - 2*k - 1; i >= k; i--) {
            int sum = sums[i+2*k] - sums[i+k];
            if (sum >= lastSum) {
                posRight[i] = i+k;
                lastSum = sum;
            } else {
                posRight[i] = posRight[i+1];
            }
        }

        int maxSum = 0;
        for (int i = k; i <= n - 2 *k; i++) {
            int l = posLeft[i];
            int r = posRight[i];
            int sum = (sums[l+k] - sums[l]) + (sums[i+k] - sums[i]) + (sums[r+k] - sums[r]);
            if (sum > maxSum) {
                result = new int[]{l,i,r};
                maxSum = sum;
            }
        }

        return result;
    }
}