剑指 Offer 42. 连续子数组的最大和——从这题开始学习动态规划

这题是典型的动态规划题目，新手可以从这题开始入手动态规划，从动态规划的概念 到 解题思路 到最后的优化方式。

一、题目

剑指 Offer 42. 连续子数组的最大和

二、分析

动态规划入门文章参考：什么是动态规划（Dynamic Programming）？动态规划的意义是什么？

• 1.能不能使用动态规划
  一个问题能不能动态规划 有以下三点:

  • 1.重叠子结构：一个大的问题能否拆成若干小问题
  • 2.满足无后效性： 历史状态不会影响将来的状态，未来的状态和历史无关，当前状态 决定历史状态。
  • 3.最优子结构： 问题的最优解 可否有子问题的最优解推出

• 2.如何使用动态规划

   【dp三连】
     1.我是谁？  转态设计
     2.我从哪里来 我到哪里去  转态转移 
        我从哪里来 代表pull类型的转移  (由顶至底)
        我到哪里去 代表pushl类型的转移 (由底至顶)
        这两个问题在实际求解 考虑清楚一个就行了。
     
     3. 明确初始条件。  base case
  

• 3.结合本题分析

  求所有子数组的和的最大值  
  => 假设 数组长度 为n  求长度为n的所有子数组的和的最大值   
  => 可以先求 前 n -1 所有子数组的和的最大者 再与 n 比较
  => 问题可以拆分成 若干重叠子问题  
  =>满足重叠子问题
  
  => 我只关心 n-1的所有子序列的和 的到n的子数组和 而不必关系 n-1 以前的是怎么求得的  ， n-1 =>n   n-1当前状态 ， n未来状态， n-1 以前的是历史状态。 n-1以前的历史状态不影响n的未来状态，当前状态 n-1 可以推出未来转态。
  => 满足无后效性
  
  =>子问题的最大值 可以得到 原问题的最大值 
  => 满足无后效性
  
  => 综上 可以使用动态规划
  

• 4.算法设计

  1.我是谁 -> 状态设计
  
      设 f(i) 是以下标i结尾的所有子数组的和的最大值
  
  2.我到哪里去
      f(i+1) = nums[i+1]          ,f(i) <0
             = f(i) + nums[i+1] ,f(i) >0
      
      即动态转转移方程
      dp[i+1] = nums[i+1]  ,dp[i] <0
              = nums[i+1] + dp[i] , dp[i] >=0
  3.明确初始值
    f(0) = nums[0] 只有一个 就是nums[0]
  

• 5.动态规划优化
  动态规划一般都有两种优化的方法 ：

  • ①滚动数组 ： 如果题目允许我们修改原数组 我们直接使用原数组当做dp数组。避免重新创建一个dp 可以将空间复杂度将为O(1)
  • ②变量替换 ： 如果不允许修改原数组，且我们发现 dp[i] 只与 dp[i-1]或者前几个dp值有关，我们可以创建对应数量的变量,不断交替更新即可，不用创建整个dp。

三、题解

• ①标准的动态规划

  /*我们如何判断一个问题能否使用DP解决呢？ :  能将大问题拆成几个小问题，且满足无后效性、最优子结构性质。
     1.大问题能否拆成小问题  ： 求所有子数组的和的最大值 f(n)  => 能找拆成 求 n-1个子数组的和的最大值 f(n-1)  => 拆成求 n-2个子数组的和的最大值
     2，是否满足最后子结构 和无后效性 ：  如果当前状态是 f(n-1) f(n-1) 可以由 f(n-2) 推出。 当前状态f(n-1) 可以影响 未来状态f(n) 但是未来状态f(n) 不受历史状态  f(n-1)的影响。 满足于后效性  和最优子结构
  
    dp 三连 ： 1.我是谁？  2.我从来哪里来？ 3.明确初始条件。  
  */
  public int maxSubArray(int[] nums) {
  
      //特例处理
      int len =  nums.length; 
      if(nums == null || len == 0) return 0;
  
  
      //1.我是谁？ dp[i] 是以 nums[i]结尾的所有子数组的和的最大值
      int[] dp = new int[len];
  
      //3.明确初始条件
      dp[0] = nums[0];
  
      //2.我从哪里来  dp[i] = nums[i]  , dp[i-1] < 0  
      //                   dp[i-1] + nums[i] dp[i-1]>0   //这里用到了dp[i-1] 所以i>=1 从而需要明确base 初始条件
  
      //记录max  有些动态规划结果 是dp[len-1]  有些不是， 需要具体看状态的定义，看dp列表
      int max = nums[0];
      for(int i  = 1; i < len ; i++){
          dp[i] = (dp[i-1])<0? nums[i] : nums[i]+dp[i-1];
          max = Math.max(max,dp[i]);
      }
      return max;
  }
  

• ②动态规划优化：滚动数组

  //①滚动数组 ： 如果题目允许我们修改原数组 我们直接使用原数组当做dp数组。避免重新创建一个dp  可以将空间复杂度将为O(1)
  
  // 直接用原数组当做dp数组
  public int maxSubArray(int[] nums) {
  
      //特例处理
      int len = nums.length;
      if(nums == null || len == 0) return 0;
  
      int max = nums[0];
  
      //使用原数组当做dp数组
      for(int i = 1 ; i < len; i++){
          nums[i] = (nums[i-1] < 0)? nums[i] : nums[i-1]+nums[i];
          max = Math.max(max,nums[i]);
      }
      return max;
  }
  

• ③动态规划优化：变量替换

  //②变量替换 ： 如果不允许修改原数组，且我们发现 dp[i] 只与 dp[i-1 或者前几个dp值有关，我们可以创建对应数量数的变量 不断交替更新即可，不用创建整个dp
  
  //本例dp状态方程中，dp[i] 只和dp[i-1]相关，我们可以定义一个变量 并不断的更新它，达到dp数组的效果
  public int maxSubArray(int[] nums) {
      //特例处理
      int len = nums.length
      if(nums == null || len == 0) return 0;
  
      int max = nums[0];
      int sum = 0; // 替换dp列表
  
      for(int i = 0; i < len; i++){
  
          sum =  sum < 0? nums[i] : nums[i]+sum; //在第一次的时候，sum是替换dp[i-1] 计算后更新为dp[i]
          max = Math.max(sum,max);
      }
      return max;
  }
  

四、复杂度

• 标准dp：时间复杂度O(n)，空间复杂度O(n)， n是数组元素个数。
• 优化dp：时间复杂度O(n)，空间复杂度O(1)。