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元起，快前往官网查看详情吧

分享标题：leetcode刷题logday53-创新互联
文章URL：http://azwzsj.com/article/igoih.html

leetcode刷题logday53-创新互联

其他资讯