leetcode刷题logday53-创新互联

• 1143. 最长公共子序列
  【思路】分别遍历两个数组，如果元素相等，长度 +1，长度不相等，就比较两个数组的前一个元素哪个最长公共子序列长。

  

  创新互联为企业级客户提高一站式互联网+设计服务，主要包括成都做网站、网站建设、外贸营销网站建设、APP应用开发、微信平台小程序开发、宣传片制作、LOGO设计等，帮助客户快速提升营销能力和企业形象，创新互联各部门都有经验丰富的经验，可以确保每一个作品的质量和创作周期，同时每年都有很多新员工加入，为我们带来大量新的创意。 

  var longestCommonSubsequence = function(text1, text2) {let dp = new Array(text1.length + 1).fill().map(() =>Array(text2.length + 1).fill(0));
  
      for (let i = 1; i<= text1.length; i++) {// 要小于等于长度，因为比较的是当前元素的前一个，小于长度的话最后一个元素没办法比较
          for (let j = 1; j<= text2.length; j++) {if (text1[i - 1] === text2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1
              else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
          }
      }
      
      return dp[text1.length][text2.length];
  };

• 1035. 不相交的线
  【思路】线就是两数相等，不相交就是按顺序来，本质和上一道题一样～

var maxUncrossedLines = function(nums1, nums2) {let dp = new Array(nums1.length + 1).fill().map(() =>Array(nums2.length + 1).fill(0));

    for (let i = 1; i<= nums1.length; i++) {for (let j = 1; j<= nums2.length; j++) {if(nums1[i - 1] === nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1
            else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[nums1.length][nums2.length];
};

• 53. 大子序和（动态规划）
  【思路】dp[i] 代表到第 i 个元素为止大的子序列和。计算 dp[i] 时考虑两种情况：上一个的和加上现在的元素（dp[i] = dp[i - 1] + nums[i]）或者从当前元素开始计算（dp[i] = nums[i]），取两种情况的大值即可。

  // 贪心
  var maxSubArray = function(nums) {let res = -Infinity, count = 0;
      for (let i = 0; i< nums.length; i++){count += nums[i];
          if (count >res) res = count;
          if (count< 0) count = 0;  // 如果总和小于 0 了，就下一个位置开始重新计和
      }
      return res;
  };
  
  // 动规
  let maxSubArray = function(nums) {let dp = new Array(nums.length).fill(0);
    dp[0] = nums[0];
  
    for (let i = 1; i< nums.length; i++) {dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
    }
  
    return Math.max(...dp);
  }

参考代码随想录：https://www.programmercarl.com/

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧