題目描述

給定數(shù)組

由正整數(shù)組成，找到三個(gè)互不重疊的子數(shù)組的最大和。 每個(gè)子數(shù)組的長(zhǎng)度為 ，我們要使這 個(gè)項(xiàng)的和最大化。 返回每個(gè)區(qū)間起始索引的列表（索引從 0 開(kāi)始）。如果有多個(gè)結(jié)果，返回字典序最小的一個(gè)。

示例1

輸入： [1,2,1,2,6,7,5,1], 2 輸出： [0, 3, 5] 解釋： 子數(shù)組 [1, 2], [2, 6], [7, 5] 對(duì)應(yīng)的起始索引為 [0, 3, 5]。 我們也可以取 [2, 1], 但是結(jié)果 [1, 3, 5] 在字典序上更大。

提示

• 的范圍在[1, 20000]之間。
• 的范圍在[1, 65535]之間。
• 的范圍在 [1, floor(nums.legth / 3)]之間。

題解

首先看數(shù)據(jù)范圍，這題不能使用暴力，暴力時(shí)間復(fù)雜度是

，一定會(huì)超時(shí)，所以考慮使用動(dòng)態(tài)規(guī)劃求解。

下面考慮一般情況，也就是求解劃分成

個(gè)不重疊數(shù)組的最大和。

假設(shè)到第

個(gè)元素為止，一共已經(jīng)產(chǎn)生了 個(gè)不重疊數(shù)組，那么令 表示這個(gè)不重疊數(shù)組的最大和。

然后就要尋找狀態(tài)轉(zhuǎn)移方程。對(duì)于第

個(gè)元素，分為兩種情況，可取可不取。

如果取，那就說(shuō)明

是第 個(gè)子數(shù)組的最后一個(gè)元素，那么轉(zhuǎn)移方程為：

也就是說(shuō)，從

到 ，這 個(gè)元素構(gòu)成了第 個(gè)子數(shù)組，那我們只需要求到第 個(gè)元素為止，產(chǎn)生 個(gè)不重疊數(shù)組的最大和即可。

如果不取，那問(wèn)題就變成了求到第

個(gè)元素為止，產(chǎn)生 個(gè)不重疊數(shù)組的最大和，那么轉(zhuǎn)移方程為：

當(dāng)然這題還需要你還原出最大和的情況下，所有子數(shù)組的起始元素下標(biāo)，所以需要另外用一個(gè)數(shù)組保存一下每一步的最優(yōu)下標(biāo)。

同樣，假設(shè)到第

個(gè)元素為止，一共已經(jīng)產(chǎn)生了 個(gè)不重疊數(shù)組，用 表示第 個(gè)子數(shù)組的末尾元素下標(biāo)。

那么按照上面的推斷，如果取第

個(gè)元素，那么 ；否則的話 。

最后就是根據(jù)

數(shù)組還原答案了。

首先最后一個(gè)子數(shù)組的末尾元素下標(biāo)一定是

，那么它的起始元素下標(biāo)就是 ，然后前一個(gè)子數(shù)組末尾元素下標(biāo)就是 ，依次下去，直到第一個(gè)子數(shù)組被求解完畢。

代碼

class Solution { public:vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {int len = nums.size(), N = 3;int sum[len], s = 0;for (int i = 0; i < k; ++i) {s += nums[i];sum[i] = 0;}sum[k-1] = s;for (int i = k; i < len; ++i) {s += nums[i] - nums[i - k];sum[i] = s;}int dp[len][N+1], path[len][N+1];memset(dp, 0, sizeof dp);dp[k-1][1] = sum[k-1];path[k-1][1] = k - 1;for (int i = k; i < len; ++i) {for (int j = 1; j <= N; ++j) {dp[i][j] = dp[i-1][j];path[i][j] = path[i-1][j];if (dp[i][j] < dp[i-k][j-1] + sum[i]) {dp[i][j] = dp[i-k][j-1] + sum[i];path[i][j] = i;}}}vector<int> res;int idx = path[len-1][N];res.push_back(idx - k + 1);for (int i = N - 1; i > 0; --i) {idx = path[idx-k][i];res.push_back(idx - k + 1);}reverse(res.begin(), res.end());return res;} };

后記

可以看到，時(shí)間和空間還有提升的余地。想到的可能優(yōu)化方法是類(lèi)似于0-1背包那樣，去掉動(dòng)態(tài)規(guī)劃數(shù)組的第二個(gè)維度，來(lái)優(yōu)化空間復(fù)雜度。

但是這是有些問(wèn)題的，暫時(shí)并沒(méi)有想到不增加時(shí)間復(fù)雜度下減少空間開(kāi)銷(xiāo)的方法，歡迎大家提出自己的想法。

總結(jié)

以上是生活随笔為你收集整理的数组最大可以开多大_每日算法系列【LeetCode 689】三个无重叠子数组的最大和的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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