剑指 Offer 42. 连续子数组的最大和

落日映苍穹つ 2022-10-29 01:51 113阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]  
[题解][Link 1]

//解法一：分治
    class Solution {
        
        public int maxSubArray(int[] nums) {
        
            return merge(nums, 0, nums.length - 1);
        }
        public int merge(int[] nums, int l, int r){
        
            if(l == r)
                return nums[l];
            int mid = l + r >> 1;
            int leftSum = merge(nums, l, mid);
            int rightSum = merge(nums, mid + 1, r);
            int CrossSum = Cross(nums, l, r, mid);
            return Math.max(leftSum, Math.max(rightSum, CrossSum));
        }
    
        public int Cross(int[] nums, int l, int r, int mid){
        
            if(l == r)
                return nums[l];
            int curSum = 0;
            int left = Integer.MIN_VALUE;
            for(int i = mid; i >= l; i--){
        
                curSum += nums[i];
                left = Math.max(left, curSum);
            }
    
            int right = Integer.MIN_VALUE;
            curSum = 0;
            for(int i = mid + 1; i <= r; i++){
        
                curSum += nums[i];
                right = Math.max(right, curSum);
            }
            return left + right;
        }
    }

//解法二：动态规划  最优解
    class Solution {
        
        public int maxSubArray(int[] nums) {
        
            int n = nums.length;
            int ans = Integer.MIN_VALUE;
            if(n == 1)
                return nums[0];
            ans = Math.max(ans, nums[0]);
            for(int i = 1; i < n; i++){
        
                if(nums[i - 1] >= 0)
                    nums[i] += nums[i - 1];
                ans = Math.max(ans, nums[i]);
            }
            return ans;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]: /images/20221024/9dbb4c9d21904e52b645bb3d106bf1c0.png
[Link 1]: https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/solution/tan-xin-fen-zhi-dong-tai-gui-hua-fa-by-luo-jing-yu/