头像

带翅膀的猫

时光荏苒,我们一直都在

《LeetCode刷题(Easy Rank):53. Maximum Subarray》

 1月前  •   LeetCode  •     •   22  •   0

Question:

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

JAVAInput: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:

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

Solution:

很明显这是一个DP问题,状态转移方程为:sum = max{nums[i],nums[i]+sum}。sum为局部最优,我们需要得到全局最优。

JAVAclass Solution {
    public int maxSubArray(int[] nums) {
        int currMax = nums[0];
        int allMax = nums[0];
        for ( int i = 1; i < nums.length; i++) {
            currMax = Math.max(nums[i], currMax + nums[i]);//得到局部最大值
            if (currMax > allMax) {//和全局最大值比较
                allMax = currMax;//获得全局最大值
            }
        }
        return allMax;//返回全局最大值
    }
}

Divide:

《算法导论》在归并算法中详细介绍了最长子数组问题。感兴趣的可以去翻一下,有助于理解。代码有点长呢。

JAVAclass Solution {
    public int maxSubArray(int[] nums) {
       int low=0,high=nums.length-1;
       return getMaxSum(nums,low,high);
    }
    
    public int getMaxSum(int[] nums,int low,int high){
        if(low==high){
            return nums[low];
        }
        int mid = (low+high)/2;
        int leftSum = getMaxSum(nums,low,mid);
        int rightSum = getMaxSum(nums,mid+1,high);
        int crossSum = getCrossSum(nums,low,mid,high);
        if(leftSum>=rightSum&&leftSum>=crossSum){
            return leftSum;
        }else{
            if(rightSum>=leftSum&&rightSum>=crossSum){
                return rightSum;
            }else{
                return crossSum;
            }
        }
        
    }
    
    public int getCrossSum(int[] nums,int low,int mid,int high){
        int sum=0;
        int leftSum=Integer.MIN_VALUE;
        int i=mid;
        for(;i>=low;i--){
            sum = sum+nums[i];
            if(sum>leftSum){
                leftSum = sum;
            }
        }
        int j=mid+1;
        int rightSum = Integer.MIN_VALUE;
        sum=0;
        for(;j<=high;j++){
            sum = sum+nums[j];
            if(sum>rightSum){
                rightSum=sum;
            }
        }
        return leftSum+rightSum;
    }
}

 

上一篇:
下一篇:

 评论


 已有0条评论

    还没有任何评论,你来说两句吧!