欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode------Maximum SubArray

程序员文章站 2022-07-15 19:48:50
...

LeetCode------Maximum SubArray

解法1

分治法Divide and Conquer Approach来解,这个分治法的思想就类似于二分搜索法,我们需要把数组一分为二,分别找出左边和右边的最大子数组之和,然后还要从中间开始向左右分别扫描,求出的最大值分别和左右两边得出的最大值相比较取最大的那一个,代码如下:

/*
     * 分治法的思想就类似于二分搜索法,我们需要把数组一分为二,
     * 分别找出左边和右边的最大子数组之和,然后还要从中间开始向左右分别扫描,
     * 求出的最大值分别和左右两边得出的最大值相比较取最大的那一个
     * 
     * 考虑三部分:
     *      leftMax:左边最大子数组和
     *      rightMax:右边最大子数组
     *      midMax:从中间分别从两边扫描left~mid-1 mid+1~right
     */
    public int maxSubArray(int[] nums) {
        if (nums.length == 0) return 0;
        return helper(nums, 0, nums.length - 1);
    }
    public int helper(int[] nums, int left, int right) {
        if (left >= right) return nums[left];
        int mid = left + (right - left) / 2;

        //分别找出左右两部分最大和
        int leftMax = helper(nums, left, mid - 1);
        int rightMax = helper(nums, mid + 1, right);

        //从中间往两边扫描,tmp保存临时的midMax
        int midMax = nums[mid];
        int tmp = midMax;
        for (int i = mid - 1; i >= left; --i) {
            tmp += nums[i];
            midMax = Math.max(midMax, tmp);
        }
        tmp = midMax;
        for (int i = mid + 1; i <= right; ++i) {
            tmp += nums[i];
            midMax = Math.max(midMax, tmp);
        }
        //返回三部分的最大值
        return Math.max(midMax, Math.max(leftMax, rightMax));
    }

解法2

O(n)的解法,定义两个变量rescurSum,其中res保存最终要返回的结果,即最大的子数组之和,curSum初始值为0,每遍历一个数字num,比较curSum + numnum中的较大值存入curSum,然后再把res和curSum中的较大值存入res,以此类推直到遍历完整个数组,可得到最大子数组的值存在res中,代码如下:

/*
     * O(n)的解法,定义两个变量res和curSum:
     *      res保存最终要返回的结果,即最大的子数组之和;
     *      curSum初始值为0,每遍历一个数字num,比较curSum + num和num中的较大值存入curSum,然后再把res和curSum中的较大值存入res,
     *      以此类推直到遍历完整个数组,可得到最大子数组的值存在res中
     */

    public int maxSubArray2(int[] nums) {
        int res = Integer.MIN_VALUE;
        int curSum = 0;
        for(int num : nums) {
            curSum = Math.max(curSum+num, num);
            res = Math.max(res,curSum);
        }
        return res;
    }

解法3

动态规划
LeetCode------Maximum SubArray

    //动态规划:其实跟上面O(n)解法思想是一样的
    public int maxSubArray3(int[] nums) {
        int maxLocal = nums[0];
        int global = nums[0];
        for(int i =1;i<nums.length;i++) {
            maxLocal = Math.max(nums[i],nums[i]+maxLocal);
            global = Math.max(global, maxLocal);
        }
        return global;
    }