剑指offer面试题42连续子数组的最大和（动态规划、简单）

连续子数组的最大和

个人博客

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

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

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


题解

• 动态规划

  
  
  
  
  • 算法思想
    
    
    
    • 状态转移方程
      
      
      
      • 当 dp【i-1】> 0时，dp【i】 = dp【i-1】+nums【i】
      
      
      • 当 dp【i-1】<= 0时，dp【i】 = nums【i】
      
      
      
      
    
    
    • 初始状态
      
      
      
      • dp【0】= nums【0】
      
      
      
      
    
    
    • 返回值
      
      
      
      • 返回 dp 列表中最大值，代表全局最大值
      
      
      
      
    
    
    
    
  
  
  • 复杂度分析
    
    
    
    • 时间复杂度 O(n)
    
    
    • 空间复杂度 O(1)
    
    
    
    
  
  

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


  

  
  

总结

• 判断是否能用动态规划解决问题的重要条件是
  
  
  
  • 可以分解为子问题（我自己加的）
  
  
  • 重复子问题（相比于回溯是否有优化的地方在于判断是否有子问题）
  
  
  • 最优子结构
  
  
  • 无后效性（一般都会成立）