1.求兩個子數組最大的累加和
給定一個數組，其中有很多子數組，在所有兩個子數組的組合中，找到相加和最大的一組，要求兩個子數組無重合部分，最后返回累加和
要求時間復雜度O(N) 算法原型：求一個數組中子數組的最大累加和 思路：設置一個res記錄最大的和的值，一個cur記錄當前和的值，當res小于cur時，將res替換為cur，否則cur繼續累加下一個數，當cur值為負時，將cur置為0，繼續累加下一個數 即例如一個數組是[3,4,1,-1,-3,-5,2,8,-6],則 cur：3,7,8,7,4,0,2,10,4 res：3,7,8,8,8,8,8,10,10 即該數組的子數組最大和為10 該算法原型代碼為： public static int maxSum(int[] arr){if(arr == null || arr.length == 0){return 0;}int res = arr[0];int cur = arr[0];for(int i = 1; i< arr.length; i++){cur = cur < 0 ? 0 : cur;cur += arr[i];res = Math.max(res, cur);}return res; }
本題是求兩個不重合的子數組的最大累加和，思路是將數組中每個值設置為一個分割點，左邊為一個子數組，右邊為一個子數組，分別求其左右兩邊子數組的最大累加和，遍歷數組中的每一個數即可求出結果。 為了實現時間復雜度為O(N)的要求，可以設置兩個輔助數組，分別記錄每個數的左右兩邊的子數組的最大累加和，之后即可直接從兩個輔助數組中求出兩個不重合的子數組最大累加和 也可以直接設置一個記錄右邊子數組的最大累加和的子數組，因為是從左向右遍歷，所以可以直接省去記錄左邊的輔助數組。 如上述示例數組的右輔助數組為：[10,10,10,10,10,10,8,-6,0] 本題的示例代碼為： public static int maxSum(int[] arr){if(arr == null || arr.length == 0){return 0;}int[] h = new int[arr.length];h[arr.length - 1] = arr[arr.length - 1];int cur = arr[arr.length - 1];for(int i = arr.length - 2; i >= 0; i--){cur = cur < 0 ? 0 : cur;cur += arr[i];h[i] = Math.max(h[i+1], cur);}int res = arr[0] + h[1];int lmax = arr[0];cur = arr[0];for(int i = 1; i<arr.length - 1; i++){cur = cur < 0 ? 0 : cur;cur += arr[i];lmax = Math.max(lmax, cur);res = Math.max(res, lmax + h[i+1]);}return res; }
2.未排序正數數組中累加和為給定值的最長子數組長度
給定一個數組arr，該數組無序，但每個值均為正數，在給定一個正數k，求arr的所有子數組中所有元素相加和為k的最長子數組的長度
例如，arr=[1，2，1，1，1],?k?=?3
則累加和為3的最長子數組為[1,1,1]，結果返回為3
要求時間復雜度O(N)，額外空間復雜度O(1) 思路：建立兩個指針L和R，兩個全局變量sum和len，若sum<=k,R++,否則L++，當sum==k時記錄len
代碼： public static int getMaxLength(int[] arr, int k){if(arr == null || arr.length == 0 || k <= 0){return 0;}int left = 0;int right = 0;int sum = arr[0];int len = 0;while(right < arr.length){if(sum == k){len = Math.max(len, right-left+1);sum -= arr[left++];}else if(sum < k){right++;if(right == arr.length){break;}sum += arr[right];}else{sum -= arr[left++];}}return len; }
3.未排序數組中累加和為給定值的最長子數組系列問題? 給定一個無序數組arr，其中元素可正、可負、可0，給定一個整數k，求arr所有的子數組中累加和為k的最長子數組長度。
思路：建立一個輔助數組sum[],sum[i]表示arr數組中前i項之和，若i<j,且sum[i] + k = sum[j],則k等于arr數組中第i+1項到第j項之和。即若必須以第j項為結尾的累加和為k的最長子數組。
public static int maxLength(int[] arr, int k){if(arr == null || arr.length == 0){return 0;}HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();map.put(0,-1); // 這里很重要，如果沒有這條規定，則所有從頭開始累積的數組失效int len = 0;int sum = 0;for(int i = 0; i<arr.length;i++){sum += arr[i];if(map.containsKey(sum - k)){len = Math.max(i - map.get(sum - k), len);}if(!map.containsKey(sum)){map.put(sum,i);}}return len; }給定一個無序數組arr，其中元素可正可負可0，求arr所有的子數組中正數與負數個數相等的最長子數組長度。
相當于：把數組中所有正數置為1，所有負數置為-1，求累加和為0的最長子數組


給定一個無序數組arr，其中元素只能是1或是0，求arr所有的子數組中0和1個數相等的最長子數組長度。
要求時間復雜度為O(N)
相當于：將數組中所有0重置為-1，求累加和為0的最長子數組

4.未排序數組中累加和小于等于給定值的最長子數組長度
給定一個無序數組arr，給定一個整數k，求arr所有的子數組中累加和小于等于k的最長子數組長度
例如：arr = {3,-2,-4,0,6}, k=-2,相加和小于或等于-2的最長子數組為{3,-2,-4,0}，所以結果返回4.要求時間復雜度為O(N*logN)
arr[] = {3,2,-3,2,-2,6,-3,1}
sum[] = {3,5,2,4,2,8,5,6}
h[] = {3,5,5,5,5,8,8,8}

public static int maxLength(int[] arr, int k){int[] h = new int[arr.length + 1];int sum = 0;h[0] = sum;for(int i = 0; i != arr.length; i++){sum += arr[i];h[i+1] = Math.max(sum,h[i]);}sum = 0;int res = 0;int pre = 0;int len = 0;for(int i = 0; i!=arr.length;i++){sum += arr[i];pre = getLessIndex(h, sum - k);len = pre == -1 ? 0 : i - pre + 1;res = Math.max(res, len);}return res; }public static int getLessIndex(int[] arr, int num){ //在輔助數組中找到第一個大于等于h的位置int low = 0;int high = arr.length - 1;int mid = 0;int res = -1;while(low <= high){mid = (low + high) / 2;if(arr[mid] >= num){res = mid;high = mid -1;}else{low = mid +1;}}return res; }

總結

以上是生活随笔為你收集整理的有关子数组最大累加和的算法小结的全部內容，希望文章能夠幫你解決所遇到的問題。

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