題目
思路：首先是長度為k的子數組的和。這個好計算。題目要求返回的是三個和最大的子數組的第一個數字的下標。下標要盡可能小。如果只要求這樣，題目就很簡單了。還有個要求是各個子數組不重疊。要想不重疊首先得要求下標不重疊。子數組1下標是:0,1,2；子數組2下標如果是1,2,3那肯定會重疊。其次要計算出每個子數組的最大值，最小值。在找下個子數組的時候，范圍不能在這之間。我應該是傻眼了。需要考慮的因素比較多。看別人怎么解吧。
學習：看了別人的解法，明白題目意思了解錯了。不重疊的子數組就是指下標不重疊，而不是各個值不重疊。要返回的三個下標(idx1,idx2,idx3) 滿足idx2>=idx1+kidx2>=idx1+k 并且 idx3>=idx2+kidx3>=idx2+k。
還要學習的一點是：當計算了長度為k的子數組的和，計算之后其實得到了一個sums的數組。sums[i]表示以i為起點的長度為k的子數組的和。sums的長度是n-k+1。如此看待問題會比較簡單一些。
對于求這三個下標我一開始的做法是：

int max1 = sums[0],max2 = sums[0+k],max3 = sums[0+2*k];int idx1 = 0,idx2 = k,idx3 = 2*k;for (i = 1; i < k; i++) {if (sums[i] > max1) {max1 = sums[i];idx1 = i;}if (i+k <n && sums[i+k] > max2) {max2 = sums[i+k];idx2 = i+k;}if (i+2*k < n && sums[i+2*k] > max3) {max3 = sums[i+2*k];idx3 = i+2*k;}}

這樣做的問題是：可能idx2沒有變化，idx1變化了。這樣他們的差值就不是k，就不能符合條件了。所以需要固定idx2的位置。n=sums.length；那么idx1∈[0,idx2?k]idx1∈[0,idx2?k] 并且 idx3∈[idx2+1,n?1]idx3∈[idx2+1,n?1]。而idx2能夠取值的范圍是[k,n?k?1][k,n?k?1]。(n是原始數組長度)。

當idx2位置固定，對于idx1應該是[0,idx2-k]那個最大數的下標。這個問題可以用動態規劃解決。用一個數組先保存從[0,當前位置]值最大的下標。動態轉移方程式： 如果sums[i]>sums[left[i?1]]sums[i]>sums[left[i?1]]，則left[i]=ileft[i]=i；否則left[i]=left[i?1]left[i]=left[i?1]。當然這里不用動態規劃，那就每次循環一下從0到idx2-k找到最大值的下標。

右邊也是一樣。當idx2位置固定，對于idx3應該是[idx2+1,n-1]那個最大數的下標。用動態規劃解決。用一個數組先保存從[當前位置,n-1]值最大的下標。動態轉移方程式： 如果sums[i]>=sums[right[i+1]]sums[i]>=sums[right[i+1]]，則right[i]=iright[i]=i；否則right[i]=right[i+1]right[i]=right[i+1]。這里的條件是>=>=是因為，結果要求返回下標最小值。

學習鏈接

public int[] maxSumOfThreeSubarrays(int[] nums, int k) {int n = nums.length;//計算和，因為入參都是正數，所以不需要初始化sums，否則可以都初始化為Integer.MIN_VALUE;int[] sums = new int[n];//這步可以優化//0,1 1,2 2,3 3,4 4,5 5,6int sum = 0;for (int i = 0; i <n; i++) {sum += nums[i];if(i>=k) sum -= nums[i-k];if(i>=k-1) sums[i-k+1] = sum; }//與左邊的數組比較int[] left = new int[n-k+1];int best = 0;for(int i=0;i<left.length;i++){if(sums[i]>sums[best]) best = i;left[i] = best;}//跟右邊的數組比較int[] right = new int[n-k+1];best = right.length - 1;for(int i = right.length -1;i>=0;i--){if(sums[i]>=sums[best]) best = i;right[i] = best;}int idx1 = -1,idx2 = -1,idx3 = -1;for (int j = k; j < right.length-k; j++) {int l = left[j-k],r = right[j+k];if(idx1==-1 || (sums[idx1]+sums[idx2]+sums[idx3] < sums[l]+sums[j]+sums[r])){idx1 = l;idx2 = j;idx3 = r;}}return new int[]{idx1,idx2,idx3};}

復雜度分析：時間復雜度O(n)，空間復雜度O(n)。

總結

以上是生活随笔為你收集整理的689 Maximum Sum of 3 Non-Overlapping Subarrays的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。