leetcode 1031. Maximum Sum of Two Non-Overlapping Subarrays

本文主要是介绍leetcode 1031. Maximum Sum of Two Non-Overlapping Subarrays，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

leetcode 1031. Maximum Sum of Two Non-Overlapping Subarrays

题意：给你一个数组，再给你一个L，M，求在这个数组里面，两个不重合的长度分别为L，M的最的最大和。

思路：

先预处理一个dp[i][2];

dp[i][0]表示以i为开头，长度为L的值。

dp[i][1]表示以i为开头，长度为M的值。

在两层for，遍历i，j分别表示两个数组的头，只要两个数组不重合，就是合适的数组。

最后求个最大值就好了。

class Solution {
public:int maxSumTwoNoOverlap(vector<int>& A, int L, int M) {vector<int> sum(A.size(), 0);vector<vector<int>> dp(A.size(), vector<int>(2, 0));//sum[0] = A[0];//for (int i = 1; i<A.size(); i++)//	sum[i] = sum[i - 1] + A[i];//for (int i = 0; i < A.size(); i++)//	cout << sum[i] << '\t';//cout << endl;for (int i = 0; i<A.size(); i++){for (int j = 0; j < L && i+j<A.size(); j++)dp[i][0] += A[i + j];for (int j = 0; j < M && i+j<A.size(); j++)dp[i][1] += A[i + j];}//for (int i = 0; i < A.size(); i++)//	cout << dp[i][0] << '\t';//cout << endl;//for (int i = 0; i < A.size(); i++)//	cout << dp[i][1] << '\t';//cout << endl;int ans = 0;for (int i = 0; i<A.size(); i++){for (int j = 0; j<A.size(); j++){if (i<j && i+L <=j)ans = max(ans, dp[i][0] + dp[j][1]);if (i>j && j+M<=i)ans = max(ans, dp[i][0] + dp[j][1]);}}return ans;}
};

 

这篇关于leetcode 1031. Maximum Sum of Two Non-Overlapping Subarrays的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---