Day 53 | 1035. 不相交的线 & 53. 最大子数组和

1035. 不相交的线

 本题其实相当于求两个数组的最长公共子序列，与昨天做的题相同。

dp解题思路：

①确定dp数组以及下标含义

        dp[i][j]：下标为[i-1]的nums1，下标为[j-1]的nums2，两个数组的最长公共子序列为dp[i][j]

②确定递推公式

        定义dp数组为dp[len1+1][len2+1]

        为了方便计算和初始化，每次比较的都是下标i-1与j-1的元素，将其赋值给dp[i][j]（注意错位一位）.

        i,j从1开始遍历（元素i-1下标为0开始遍历），

        若nums[i-1]==nums[j-1]，则dp[i][j]=dp[i-1][j-1]+1;

        若不相等，因为不要求连续，则dp[i][j]由dp[i-1][j]和dp[i][j-1]决定，取两者的最大值。

③dp数组如何初始化

        给dp[0][j],dp[i][0]初始化为0，代表初始重复子数组为0.

④确定遍历顺序

          从前向后，从上至下遍历。（i从1到len1，j从1到len2）

⑤举例推导dp数组

    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int[][] dp=new int[nums1.length+1][nums2.length+1];
        for(int i=1;i<=nums1.length;i++){
            for(int 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解题思路：

①确定dp数组以及下标含义

        dp[i]：下标为[0,i]的数组最大子数组和为sp[i]

②确定递推公式

        定义dp数组为dp[len]

        遍历数组中的每一个元素，每次遍历比较加入当前元素的数组和 和 当前元素的大小（子数组只有该元素这一个元素） 进行比较，取大值。最后返回的是dp数组中的最大值。

                        dp[i]=Math.max(dp[i-1]+nums[i],nums[i])

③dp数组如何初始化

        给dp[0]，res初始化为nums[0]

④确定遍历顺序

          因为dp[i]依赖dp[i-1]，因此为防止下标越界i从1开始向后遍历。

⑤举例推导dp数组