文章目錄

• • 1. 題目
  • 2. 解題
  • • 2.1 暴力枚舉
    • 2.2 一次遍歷

1. 題目

給出非負(fù)整數(shù)數(shù)組 A ，返回兩個(gè)非重疊（連續(xù)）子數(shù)組中元素的最大和，子數(shù)組的長(zhǎng)度分別為 L 和 M。（這里需要澄清的是，長(zhǎng)為 L 的子數(shù)組可以出現(xiàn)在長(zhǎng)為 M 的子數(shù)組之前或之后。）

從形式上看，返回最大的 V，而 V = (A[i] + A[i+1] + ... + A[i+L-1]) + (A[j] + A[j+1] + ... + A[j+M-1]) 并滿足下列條件之一：

• 0 <= i < i + L - 1 < j < j + M - 1 < A.length, 或
• 0 <= j < j + M - 1 < i < i + L - 1 < A.length.

示例 1： 輸入：A = [0,6,5,2,2,5,1,9,4], L = 1, M = 2 輸出：20 解釋：子數(shù)組的一種選擇中，[9] 長(zhǎng)度為 1，[6,5] 長(zhǎng)度為 2。示例 2： 輸入：A = [3,8,1,3,2,1,8,9,0], L = 3, M = 2 輸出：29 解釋：子數(shù)組的一種選擇中，[3,8,1] 長(zhǎng)度為 3，[8,9] 長(zhǎng)度為 2。示例 3： 輸入：A = [2,1,5,6,0,9,5,0,3,8], L = 4, M = 3 輸出：31 解釋：子數(shù)組的一種選擇中，[5,6,0,9] 長(zhǎng)度為 4，[0,3,8] 長(zhǎng)度為 3。提示： L >= 1 M >= 1 L + M <= A.length <= 1000 0 <= A[i] <= 1000

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/maximum-sum-of-two-non-overlapping-subarrays
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

2.1 暴力枚舉

• 求出前綴和，然后暴力枚舉前后兩段子數(shù)組
• 時(shí)間復(fù)雜度 $O(n^2)$

class Solution { public:int maxSumTwoNoOverlap(vector<int>& A, int L, int M) {int n = A.size(), i, j, k, maxsum = 0, sum1, sum2;vector<int> sum(A);for(i = 1; i < n; i++) sum[i] = sum[i-1]+A[i];//前綴和for(i = 0; i <= n-L; i++){sum1 = sum[i+L-1] - (i > 0 ? sum[i-1] : 0);for(j = 0; j+M-1 < i; j++)//在前{sum2 = sum[j+M-1] - (j > 0 ? sum[j-1] : 0);maxsum = max(maxsum, sum1+sum2);}for(j = i+L; j+M-1 < n; j++)//在后{sum2 = sum[j+M-1] - (j > 0 ? sum[j-1] : 0);maxsum = max(maxsum, sum1+sum2);}}return maxsum;} };

20 ms 8.4 MB

2.2 一次遍歷

參考題解區(qū)解法
時(shí)間復(fù)雜度 $O(n)$

class Solution { public:int maxSumTwoNoOverlap(vector<int>& A, int L, int M) {int n = A.size(), i;vector<int> sum(A);for(i = 1; i < n; i++) sum[i] = sum[i-1]+A[i];//前綴和int maxsum = sum[L+M-1], maxsumL = sum[L-1], maxsumM = sum[M-1];for(i = L+M; i < n; i++){maxsumL = max(maxsumL, sum[i-M]-sum[i-M-L]);//后面留一段給M， 前面 L 的最大和maxsumM = max(maxsumM, sum[i-L]-sum[i-L-M]);//后面留一段給L， 前面 M 的最大和maxsum = max(maxsum, max(maxsumL+sum[i]-sum[i-M], maxsumM+sum[i]-sum[i-L]));// 前面是 L + 當(dāng)前的 M// 前面是 M + 當(dāng)前的 L}return maxsum;} };

4 ms 8.3 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長(zhǎng)按或掃碼關(guān)注我的公眾號(hào)（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的LeetCode 1031. 两个非重叠子数组的最大和（一次遍历，要复习）*的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。