最大子序列

最大子序列

Ref: https://leetcode-cn.com/problems/maximum-sum-circular-subarray/solution/huan-xing-zi-shu-zu-de-zui-da-he-by-leetcode/

Kadane 算法

对于一个给定数组 A，Kadane 算法可以用来找到 A 的最大子段和。这里，我们只考虑非空子段。
Kadane 算法基于动态规划。

Kadane 算法的伪代码如下：

# Kadane's algorithm
ans = cur = None
for x in A:
    cur = x + max(cur, 0)
    ans = max(ans, cur)
return ans

环形最大子数组

循环数组的子段可以被分成 单区间 子段或者 双区间 子段，取决于定长数组 A 需要多少区间去表示。

例如，如果 A = [0, 1, 2, 3, 4, 5, 6] 是给定的循环数组，我们可以表示子段 [2, 3, 4] 为单区间 [2,4]；如果我们希望表示子段 [5, 6, 0, 1]，那就是双区间 [5, 6], [0, 1]。

使用 Kadane 算法，我们知道如何计算一个单区间子段的最大值，所以剩下的问题是双区间子段。
从两边出发往中间靠拢必须都是最大，那就说明中间段就是最小：

public int maxSubarraySumCircular(int[] nums) {
    int dp = nums[0], max = dp, sum = dp, min = 0;
    for(int i = 1; i < nums.length; i++){
        sum += nums[i];
        dp = nums[i] + Math.max(dp, 0);
        max = Math.max(dp, max);
    }
    dp = nums[0];
    for(int i = 1; i < nums.length -1; i++){
        dp = nums[i] + Math.min(0,dp);
        min = Math.min(dp,min);
    }
    return Math.max(sum-min,max);
}

Ref: https://pdai.tech/md/algorithm/alg-core-dynamic.html#%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E5%BA%8F%E5%88%97

最长公共子序列

对于两个子序列 S1 和 S2，找出它们最长的公共子序列。
定义一个二维数组 dp 用来存储最长公共子序列的长度，其中 dp [i][j] 表示 S1 的前 i 个字符与 S2 的前 j 个字符最长公共子序列的长度。考虑 S1i 与 S2j 值是否相等，分为两种情况:

• 当 S1i==S2j 时，那么就能在 S1 的前 i-1 个字符与 S2 的前 j-1 个字符最长公共子序列的基础上再加上 S1i 这个值，最长公共子序列长度加 1，即 dp [i][j] = dp [i-1][j-1] + 1。
• 当 S1i != S2j 时，此时最长公共子序列为 S1 的前 i-1 个字符和 S2 的前 j 个字符最长公共子序列，或者 S1 的前 i 个字符和 S2 的前 j-1 个字符最长公共子序列，取它们的最大者，即 dp [i][j] = max { dp [i-1][j], dp [i][j-1] }。

综上，最长公共子序列的状态转移方程为:

对于长度为 N 的序列 S1 和长度为 M 的序列 S2，dp [N][M] 就是序列 S1 和序列 S2 的最长公共子序列长度。
与最长递增子序列相比，最长公共子序列有以下不同点:

• 针对的是两个序列，求它们的最长公共子序列。
• 在最长递增子序列中，dp [i] 表示以 Si 为结尾的最长递增子序列长度，子序列必须包含 Si ；在最长公共子序列中，dp [i][j] 表示 S1 中前 i 个字符与 S2 中前 j 个字符的最长公共子序列长度，不一定包含 S1i 和 S2j。
• 在求最终解时，最长公共子序列中 dp [N][M] 就是最终解，而最长递增子序列中 dp [N] 不是最终解，因为以 SN 为结尾的最长递增子序列不一定是整个序列最长递增子序列，需要遍历一遍 dp 数组找到最大者。

  public int lengthOfLCS(int[] nums1, int[] nums2) {
    int n1 = nums1.length, n2 = nums2.length;
    int[][] dp = new int[n1 + 1][n2 + 1];
    for (int i = 1; i <= n1; i++) {
        for (int j = 1; j <= n2; 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[n1][n2];
  }