每日一题 - 剑指 Offer 42. 连续子数组的最大和

题目信息

时间： 2019-06-30
题目链接：Leetcode
tag：动态规划
难易程度：简单
题目描述：

输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

示例:

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]

输出: 6

解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

提示

1. 1 <= arr.length <= 10^5

2. -100 <= arr[i] <= 100

解题思路

本题难点

常见解法	时间复杂度	空间复杂度
暴力搜索	O(N^2)	O(1)
分治思想	O(NlogN)	O(logN)
动态规划	O(N)	O(1)

具体思路

动态规划

状态定义：设动态规划列表 dp ，dp[i]]代表以元素 nums[i] 为结尾的连续子数组最大和。
转移方程：若 dp[i−1]≤0 ，说明 dp[i−1] 对 dp[i] 产生负贡献，即 dp[i−1]+nums[i] 还不如 nums[i] 本身大。
- 当dp[i-1]>0时，执行dp[i]=dp[i-1] + nums[i]
- 当dp[i-1]<0时，执行dp[i]=nums[i]
初始状态：dp[0] = nums[0]

代码

class Solution {

    public int maxSubArray(int[] nums) {

        if(nums == null || nums.length == 0){

            return 0;

        }

        int sum = nums[0];

        int former = 0;//用于记录dp[i-1]的值，对于dp[0]而言，其前面的dp[-1]=0

        int cur= nums[0];//用于记录dp[i]的值

        for(int num: nums){

            if(former <= 0){

                cur = num;

            }

            if(former > 0){

                cur = former + num;

            }//这两句话等同于 cur = Math.max(former,0) + num;

            former = cur;

            sum = Math.max(sum,cur);

        }

        return sum;

    }

}

复杂度分析：

时间复杂度 O(N) ：线性遍历数组 nums 即可获得结果，使用 O(N) 时间。
空间复杂度 O(1) ：使用常数大小的额外空间。

其他优秀解答

解题思路

分治法，我们把数组nums以中间位置（mid)分为左（left)右(right)两部分. 那么有，

left = nums[0]...nums[m - 1] 和 right = nums[m + 1]...nums[n-1]

最大子序列和的位置有以下三种情况：

考虑中间元素nums[m], 跨越左右两部分，这里从中间元素开始，往左求出后缀最大，往右求出前缀最大, 保持连续性。
不考虑中间元素，最大子序列和出现在左半部分，递归求解左边部分最大子序列和
不考虑中间元素，最大子序列和出现在右半部分，递归求解右边部分最大子序列和

代码

class MaximumSubarrayDivideConquer {

  public int maxSubArrayDividConquer(int[] nums) {

      if (nums == null || nums.length == 0) return 0;

      return helper(nums, 0, nums.length - 1);

    }

    private int helper(int[] nums, int l, int r) {

      if (l > r) return Integer.MIN_VALUE;

      int mid = (l + r) >>> 1;

      int left = helper(nums, l, mid - 1);

      int right = helper(nums, mid + 1, r);

      int leftMaxSum = 0;

      int sum = 0;

      // left surfix maxSum start from index mid - 1 to l

      for (int i = mid - 1; i >= l; i--) {

        sum += nums[i];

        leftMaxSum = Math.max(leftMaxSum, sum);

      }

      int rightMaxSum = 0;

      sum = 0;

      // right prefix maxSum start from index mid + 1 to r

      for (int i = mid + 1; i <= r; i++) {

        sum += nums[i];

        rightMaxSum = Math.max(sum, rightMaxSum);

      }

      // max(left, right, crossSum)

      return Math.max(leftMaxSum + rightMaxSum + nums[mid], Math.max(left, right));

    }

}

巴特西

每日一题 - 剑指 Offer 42. 连续子数组的最大和

题目信息

解题思路

代码

其他优秀解答

最新文章

热门文章