Related: LeetCode 689 - Maximum Sum of 3 Non-Overlapping Subarrays
http://www.cnblogs.com/EdwardLiu/p/6546323.html
http://www.cnblogs.com/EdwardLiu/p/6546323.html
Given a num array, find a window of size k, that has a maximum sum of the k entries.
follow-up: Find three non-overlap windows of size k, that together has a maximum sum of the 3k entries, time complexity O(n^2)
Follow Up:
这个其实可以优化到O(n)时间。
建从左端到每个下标的最大window数组，再建从右端到每个下标的最大window数组。
再从左往右走一遍所有的size k window，将其和与上一步建的两个数组一起加起来。遍历一遍取最大值即可。
建从左端到每个下标的最大window数组，再建从右端到每个下标的最大window数组。
再从左往右走一遍所有的size k window，将其和与上一步建的两个数组一起加起来。遍历一遍取最大值即可。
4 public static int find(int[] arr, int k) { 5 int res = Integer.MIN_VALUE; 6 int len = arr.length; 7 int[] left = new int[len]; 8 9 int lsum = 0; 10 for (int i=0; i<len; i++) { 11 lsum += arr[i]; 12 if (i >= k) lsum -= arr[i-k]; 13 if (i >= k-1) left[i] = Math.max(lsum, i>=1? left[i-1] : 0);//find the window end at i with max sum 14 } 15 16 int[] right = new int[len]; 17 int rsum = 0; 18 for (int j=len-1; j>=0; j--) { 19 rsum += arr[j]; 20 if (j < len-k) rsum -= arr[j+k]; 21 if (j <= len-k) right[j] = Math.max(rsum, j<len-1? right[j+1] : 0); 22 } 23 24 int midSum = 0; 25 for (int t=k; t<=len-k-1; t++) { 26 midSum += arr[t]; 27 if (t >= k + k) midSum -= arr[t-k]; 28 if (t >= k + k - 1) { // for each size k window in the middle with sum as midSum 29 //find midSum + left[t-k] + right[t+1] that gives the max 30 res = Math.max(res, midSum + left[t-k] + right[t+1]); 31 } 32 } 33 return res; 34 }
