Description

面试题42. 连续子数组的最大和

难度简单42
输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。

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

提示：

  • 1 <= arr.length <= 10^5
  • -100 <= arr[i] <= 100

解答：
利用动态规划的思想
状态方程：当 dp[i-1] 为负数时，dp[i] = nums[i]，当 dp[i-1] 不为负数时， dp[i] = dp[i-1] + nums[i]

Solution

  1. class Solution {
  2.     public int maxSubArray(int[] nums) {
  3.          int[] dp = new int[nums.length];
  4.          dp[0] = nums[0];
  5.          int res = dp[0];
  6.          for(int i = 1; i < nums.length; i ++){
  7.             dp[i] = dp[i-1] > 0? dp[i-1] + nums[i] : nums[i];   
  8.             res = Math.max(dp[i], res);
  9.          }   
  10.          return res;        
  11. }

时间复杂度为 O(n)， 空间复杂度为 O(n)

动态规划 + 空间优化

  1. class Solution {
  2.     public int maxSubArray(int[] nums) {
  3.         int res = Integer.MIN_VALUE, maxSum = 0;
  4.         for (int i = 0; i < nums.length; i ++){
  5.             if (maxSum <= 0){   // 最大和小于等于 0，替换
  6.                 maxSum = nums[i];
  7.             }else{                
  8.                 maxSum += nums[i];
  9.             }
  10.             res = Math.max(nums[i], res);
  11.         }
  12.         return res;
  13.     }
  14. }

代码优化改进：将空间复杂度为 O(1)

  1. class Solution {
  2.         public int maxSubArray(int[] nums) {
  3.             int res = nums[0];
  4.             for(int i = 1; i < nums.length; i ++){
  5.                 nums[i] = nums[i-1] > 0 ? nums[i-1] + nums[i] : nums[i];
  6.                 res = Math.max(nums[i], res);
  7.             }
  8.             return res;
  9.         }
  10.     }

执行结果：通过
显示详情
执行用时：1 ms, 在所有 Java 提交中击败了98.69%的用户
内存消耗：44.9 MB, 在所有 Java 提交中击败了80.42%的用户