字节二面&leetcode53：最大子序和 #94

Activity

1. sisterAn

   added

   LeetCode

   字节

   on Aug 13, 2020
2. sisterAn commented on Aug 13, 2020

   

   sisterAn

   on Aug 13, 2020

   Last edited by sisterAn

   OwnerAuthor

   More actions

   解法：动态规划

   动态规划（Dynamic Programming，DP）是一种将复杂问题分解成小问题求解的策略，但与分治算法不同的是，分治算法要求各子问题是相互独立的，而动态规划各子问题是相互关联的。

   分治，顾名思义，就是分而治之，将一个复杂的问题，分成两个或多个相似的子问题，在把子问题分成更小的子问题，直到更小的子问题可以简单求解，求解子问题，则原问题的解则为子问题解的合并。

   我们使用动态规划求解问题时，需要遵循以下几个重要步骤：

   • 定义子问题
   • 实现需要反复执行解决的子子问题部分
   • 识别并求解出边界条件

   第一步：定义子问题

   动态规划是将整个数组归纳考虑，假设我们已经知道了以第 i-1 个数结尾的连续子数组的最大和 dp[i-1]，显然以第i个数结尾的连续子数组的最大和的可能取值要么为 dp[i-1]+nums[i]，要么就是 nums[i] 单独成一组，也就是 nums[i] ，在这两个数中我们取最大值

   第二步：实现需要反复执行解决的子子问题部分

   dp[n] = Math.max(dp[n−1]+nums[n], nums[n])

   第三步：识别并求解出边界条件

   dp[0]=nums[0]

   最后一步：把尾码翻译成代码，处理一些边界情况

   因为我们在计算 dp[i] 的时候，只关心 dp[i-1] 与 nums[i]，因此不用把整个 dp 数组保存下来，只需设置一个 pre 保存 dp[i-1] 就好了。

   代码实现（优化）：

   let maxSubArray = function(nums) {
       let max = nums[0], pre = 0
       for(const num of nums) {
           if(pre > 0) {
               pre += num
           } else {
               pre = num
           }
           max = Math.max(max, pre)
       }
       return max
   }

   复杂度分析：

   • 时间复杂度：O(n)
   • 空间复杂度：O(1)

   leetcode
3. RainMaker-Q commented on Aug 14, 2020

   

   RainMaker-Q

   on Aug 14, 2020

   More actions

   dp

   function longestSum(nums) {
   
     const dp = [nums[0]];
     let max = -Infinity;
     for(let i=1; i<nums.length; i++) {
       if(dp[i-1]>0) {
         dp[i] = dp[i-1] + nums[i];
         max = max > dp[i] ? max : dp[i];
       } else {
         dp[i] = nums[i];
         max = max > dp[i] ? max : dp[i];
       }
     }
     return max;
   }

   dp[i]表示以nums[i]结尾的，最大的连续值。
4. tongzk94 commented on Aug 14, 2020

   

   tongzk94

   on Aug 14, 2020

   More actions

   var maxSubArray = function(nums) {
       let max = nums[0], sum = 0;
       for(item of nums) {
           sum += item;
           max = Math.max(max, sum);
           sum = sum < 0 ? 0 : sum;
       }
       return max;
   };