首页 > 代码库 > [leetcode]Maximum Subarray

[leetcode]Maximum Subarray

2024-07-16 19:42:34   224人阅读

Maximum Subarray

 Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

click to show more practice.

More practice:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

算法思路：

思路1：最土的算法，求出所有的i ~ j的和，继而求出最大值。复杂度O(n^2)

 

思路2：一维dp，空间可以压缩到O(1)。具体思想看代码：

 1 public class Solution { 2     public int maxSubArray(int[] a) { 3         if(a == null || a.length == 0) return 0; 4         int max = a[0]; 5         int tem = 0; 6         for(int i = 0; i < a.length; i++){ 7             tem += a[i]; 8             max = Math.max(tem,max); 9             tem = Math.max(tem,0);10         }11         return max;12     }13 }
View Code

 

思路3：分治。对于每次递归，将数组分半，最大和可能存在

  1. 完全在左面部分（递归求解）
  2. 完全在右面部分（递归求解）
  3. 横跨左右两个部分（从中间(必须包含中间元素，否则左右无法连接)向两边加，记录最大值）

代码如下：

 1 public class Solution { 2      public int maxSubArray(int[] a) { 3            if(a == null || a.length == 0) return 0; 4            return maxSubArray(a,0,a.length - 1); 5        } 6        private int maxSubArray(int[] a,int begin ,int end){ 7            if(begin == end) return a[begin]; 8            int mid = (begin + end) >> 1; 9            int left = maxSubArray(a, begin, mid);10            int right = maxSubArray(a, mid + 1, end);11            int leftHalf = 0,rightHalf = 0;12            int leftMax = Integer.MIN_VALUE,rightMax = Integer.MIN_VALUE;13            for(int i = mid + 1; i <= end; i++){14                rightHalf += a[i];15                rightMax = Math.max(rightHalf, rightMax);16            }17            for(int i = mid; i >= begin; i--){18                leftHalf += a[i];19                leftMax = Math.max(leftMax, leftHalf);20            }21            return Math.max(rightMax + leftMax, Math.max(left, right));22        }23 }

分治法也是二分法的一种实现。

 


联系
我们