You've successfully subscribed to The Daily Awesome
Great! Next, complete checkout for full access to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

053. 最大子序和 - Maximum Subarray

. 1 min read

【分治】 【动态规划】

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

Example:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。

Solutions

Solution  ( 15ms)

class Solution {
  public int maxSubArray(int[] nums) {
    int res = nums[0];
    int sum = res;
    for (int i = 1, length = nums.length; i < length; i++) {
      if (sum > 0) {
        sum += nums[i];
      } else {
        sum = nums[i];
      }
      res = Math.max(res, sum);
    }
    return res;
  }
}

复杂度分析 6N

Solution  ( 7ms)

class Solution {
    public int maxSubArray(int[] nums) {
        int maxSum = nums[0];
        int curSum = 0;
        
        for (int n: nums) {
            curSum += n;
            if (curSum > maxSum) { maxSum = curSum; }
            if (curSum < 0) { curSum = 0; }
        }
        
        return maxSum;
    }
}

复杂度分析 4N

Solution 【分治】【动态规划】(9ms)

class Solution {
    public int maxSubArray(int[] nums) {
    if (nums == null || nums.length == 0) {
      return 0;
    }
    int[] dp = new int[nums.length];
    dp[0] = nums[0];
    int res = dp[0];
    for (int i = 1; i < nums.length; i++) {
      dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
      res = Math.max(dp[i], res);
    }
    return res;
  }
}