/**
 即一个给定的序列的子序列，不要求连续，就是将给定序列中零个或多个元素去掉之后得到的结果
 给定序列s1={1,3,4,5,6,7,7,8},s2={3,5,7,4,8,6,7,8,2}，s1和s2的其中一个最长公共子序列是 {3,4,6,7,8}
 0                            (如果i=0且j=0)
 dp[i][j] = dp[i-1][j-1] + 1  (如果i和j>0，且A[i]=B[j]）
 dp[i][j]=max(dp[i][j-1], dp[i-1][j]) （如果i和j>0，且A[i]!=B[j]
 len is opt[0][0]
 */
public static List cacuLenOfLcs(char[] s1, char[] s2) {
    List ansList=new ArrayList();
    int len1=s1.length;int len2=s2.length;
    int[][] opt = new int[len1 + 1][len2 + 1];
    for (int i = len1 - 1; i >= 0; i--) {
        for (int j = len2 - 1; j >= 0; j--) {
            if (s1[i] == s2[j]){opt[i][j] = opt[i + 1][j + 1] + 1;}
            else {opt[i][j] = Math.max(opt[i + 1][j], opt[i][j + 1]);}
        }
    }
    int i = 0, j = 0;
    while (i < len1 && j < len2) {
        if (s1[i] == s2[j]) {ansList.add(s1[i]);i++;j++;continue;}
        if (opt[i + 1][j] >= opt[i][j + 1]) {i++;continue;}
        else {j++;}
    }
    return ansList;
}    

/**
4,3,6,5,2,1=4,5,6,3,2,1=4,5,1,2,3,6
find tagert t ,nums[t]=3 t=1
find target j ,nums[j]=5 j=3
*/
public static void getNext(int []nums,List ansList) {
    int len=nums.length;
    //findTarget t
    int t=len-2;
    while (t>=0&&nums[t]>=nums[t+1]){t--;}
    //can stop now
    if (t<0){return;}
    //findTarget j
    int j=len-1;
    while (j>=t&&nums[t]>=nums[j]){j--;}
    swap(nums,t,j);
    reverse(nums,t+1,len-1);
    ansList.add(getStr(nums));
    getNext(nums,ansList);
}

private static void reverse(int []nums,int i,int j){while (i<=j){swap(nums,i,j);i++;j--;}}

private static void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}

private static String getStr(int []nums){String str="";for(int i=0;i<nums.length;i++){str+=nums[i];str+=",";}return str.substring(0,str.length()-1);}

    
public static int getMinDistance(String word1, String word2) {
    int len1 = word1.length();int len2 = word2.length();
    int[][] dp = new int[len1 + 1][len2 + 1];
    for (int i = 0; i <= len1; i++) {dp[i][0] = i;}
    for (int j = 0; j <= len2; j++) {dp[0][j] = j;}

    //iterate though, and check last char
    for (int i = 1; i <= len1; i++) {
        char c1 = word1.charAt(i-1);
        for (int j = 1; j <= len2; j++) {
            char c2 = word2.charAt(j-1);
            if (c1 == c2) {
                dp[i][j] = dp[i-1][j-1];
                continue;
            }
            dp[i][j] = Math.min(dp[i-1][j-1] + 1,Math.min(dp[i-1][j] + 1,dp[i][j-1] + 1));
        }
    }
    return dp[len1][len2];
}

//[−2,1,−3,4,−1,2,1,−5,4]=[4,−1,2,1]= 6
//当之前的subarray大于0时，我们认为subarray对后续是有利的，将当前元素加入subarray，
//反之若subarray小于0，则另起一个subarray
public static int getMaxSubArray(int []nums) {
    int ans=Integer.MIN_VALUE,curr=0;
    for(int i=0;i<nums.length;i++){
        curr=Math.max(nums[i], curr + nums[i]);
        ans=Math.max(curr, ans);
    }
    return ans;
}