JIAKAOBO

LeetCode

venmo
wechat

感谢赞助!

  • ㊗️
  • 大家
  • offer
  • 多多！

Problem

Given an array nums of non-negative integers, return the maximum sum of elements in two non-overlapping (contiguous) subarrays, which have lengths firstLen and secondLen. (For clarification, the firstLen-length subarray could occur before or after the secondLen-length subarray.)

Formally, return the largest V for which V = (nums[i] + nums[i+1] + … + nums[i+firstLen-1]) + (nums[j] + nums[j+1] + … + nums[j+secondLen-1]) and either:

0 <= i < i + firstLen - 1 < j < j + secondLen - 1 < nums.length, or 0 <= j < j + secondLen - 1 < i < i + firstLen - 1 < nums.length.

Example 1:

Input: nums = [0,6,5,2,2,5,1,9,4], firstLen = 1, secondLen = 2
Output: 20
Explanation: One choice of subarrays is [9] with length 1, and [6,5] with length 2.

Example 2:

Input: nums = [3,8,1,3,2,1,8,9,0], firstLen = 3, secondLen = 2
Output: 29
Explanation: One choice of subarrays is [3,8,1] with length 3, and [8,9] with length 2.

Example 3:

Input: nums = [2,1,5,6,0,9,5,0,3,8], firstLen = 4, secondLen = 3
Output: 31
Explanation: One choice of subarrays is [5,6,0,9] with length 4, and [3,8] with length 3.

Code

问题的关键是什么时候可以开始计算两个 subarray 的和

class Solution {
    public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
        int res = 0, firstSum = 0, firstMax = 0, secondSum = 0, secondMax = 0;

        for (int i = 0; i < nums.length; ++i) {
            secondSum += nums[i];
            if (i - secondLen >= 0) secondSum -= nums[i - secondLen];
            // 此时second已经有足够短的元素了, 可以构建first了
            if (i - secondLen >= 0) firstSum += nums[i - secondLen];
            if (i - secondLen - firstLen >= 0) firstSum -= nums[i - firstLen - secondLen];
            firstMax = Math.max(firstMax, firstSum);
            res = Math.max(res, firstMax + secondSum);
        }

        firstSum = firstMax = secondSum = secondMax = 0;
        for (int i = 0; i < nums.length; ++i) {
            firstSum += nums[i];
            if (i - firstLen >= 0) firstSum -= nums[i - firstLen];
            if (i - firstLen >= 0) secondSum += nums[i - firstLen];
            if (i - secondLen - firstLen >= 0) secondSum -= nums[i - firstLen - secondLen];
            secondMax = Math.max(secondMax, secondSum);
            res = Math.max(res, secondMax + firstSum);
        }
        return res;
    }
}

class Solution {
    public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
        int maxSum = 0;
        int currSum = 0;
        for (int i = 0; i < nums.length; i++) {
            currSum += nums[i];
            if (i >= firstLen) {
                currSum -= nums[i - firstLen];
            }

            if (i >= firstLen - 1) {
                int sec1 = helper(nums, 0, i - firstLen, secondLen);
                int sec2 = helper(nums, i + 1, nums.length - 1, secondLen);
                maxSum = Math.max(maxSum, currSum + Math.max(sec1, sec2));
            }
        }

        return maxSum;
    }

    public int helper(int[] nums, int start, int end, int len) {
        int currSum = 0;
        int maxSum = 0;
        int maxIndex = 0;

        for (int i = start; i <= end; i++) {
            currSum += nums[i];
            if (i - start >= len) {
                currSum -= nums[i - len];
            }

            if (i - start >= len - 1 && currSum > maxSum) {
                maxSum = currSum;
                maxIndex = i - len + 1;
            }
        }

        return maxSum;
    }
}