每日一题：两个非重叠子数组的最大和 - 刷题题解

给你一个整数数组 nums 和两个整数 firstLen 和 secondLen，请你找出并返回两个非重叠子数组中元素的最大和，长度分别为 firstLen 和 secondLen 。

长度为 firstLen 的子数组可以出现在长为 secondLen 的子数组之前或之后，但二者必须是不重叠的。

子数组是数组的一个连续部分。

题目链接：https://leetcode.cn/problems/maximum-sum-of-two-non-overlapping-subarrays/

	class Solution {
	public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
	int n = nums.length;

	// 1. 从右往左记录第二个数组能取到的最大值
	int[] rmax = new int[n];
	int[] lmax = new int[n];
	int sum = 0;
	int maxSum = 0;
	for (int i = n - 1; i >= 0; --i) {
	sum += nums[i];
	if (i <= n - secondLen) {
	maxSum = Math.max(maxSum, sum);
	rmax[i] = maxSum;
	sum -= nums[i + secondLen - 1];
	}
	}

	// 2. 从右往左记录第二个数组能取到的最大和
	sum = 0;
	maxSum = 0;
	for (int i = 0; i < n; ++i) {
	sum += nums[i];
	if (i >= secondLen - 1) {
	maxSum = Math.max(maxSum, sum);
	lmax[i] = maxSum;
	sum -= nums[i - secondLen + 1];
	}
	}

	// 3. 从左往右枚举第一个数组的各个取值
	int firstArrSum = 0;
	int ans = 0;
	for (int i = 0; i < n; ++i) {
	firstArrSum += nums[i];
	// 已经能取到第一个数组的长度
	if (i >= firstLen - 1) {
	int secondArrSum = 0;
	// 右边能取到第二个数组的长度
	if (i + 1 < n) {
	secondArrSum = rmax[i + 1];
	}

	// 左边能取到第二个数组的长度
	if (i - firstLen >= 0) {
	secondArrSum = Math.max(lmax[i - firstLen], secondArrSum);
	}

	// 更新答案
	ans = Math.max(ans, firstArrSum + secondArrSum);

	firstArrSum -= nums[i - firstLen + 1];
	}
	}

	return ans;
	}
	}