最长子序列问题

• 最大子序列
  最大子序列是要找出由数组成的一维数组中和最大的连续子序列。比如{5,-3,4,2}的最大子序列就是 {5,-3,4,2}，它的和是8,达到最大；而 {5,-6,4,2}的最大子序列是{4,2}，它的和是6。你已经看出来了，找最大子序列的方法很简单，只要前i项的和还没有小于0那么子序列就一直向后扩展，否则丢弃之前的子序列开始新的子序列，同时我们要记下各个子序列的和，最后找到和最大的子序列。

public class subArray {
    public static int getSum_SubArr(int[] arr){
        int sum=0;
        if (arr.length<=0)
            return sum;
        for (int i=0;i<arr.length;i++){
            if (sum<0){
                sum=arr[i];
            }else {
                sum+=arr[i];
            }
        }
        System.out.println("sum="+sum);
        return sum;
    }

    public static void main(String[] args){
        //int[] a={1,-2,3,10,-4,7,2,-5};
        int[] a={1,3,-8,5};
        getSum_SubArr(a);
    }
}

• 最长公共子串（LCS）
  找两个字符串的最长公共子串，这个子串要求在原字符串中是连续的。其实这又是一个序贯决策问题，可以用动态规划来求解。我们采用一个二维矩阵来记录中间的结果。这个二维矩阵怎么构造呢？直接举个例子吧："bab"和"caba"(当然我们现在一眼就可以看出来最长公共子串是"ba"或"ab")

  
  image.png
  

  我们看矩阵的斜对角线最长的那个就能找出最长公共子串。

不过在二维矩阵上找最长的由1组成的斜对角线也是件麻烦费时的事，下面改进：当要在矩阵是填1时让它等于其左上角元素加1。

image.png

这样矩阵中的最大元素就是 最长公共子串的长度。

在构造这个二维矩阵的过程中由于得出矩阵的某一行后其上一行就没用了，所以实际上在程序中可以用一维数组来代替这个矩阵。

public class Solution{
    
    // 求解两个字符号的最长公共子串
    public static String maxSubstring(String strOne, String strTwo){
        // 参数检查
        if(strOne==null || strTwo == null){
            return null;
        }
        if(strOne.equals("") || strTwo.equals("")){
            return null;
        }
        // 矩阵的横向长度
        int len1 = strOne.length();
        // 矩阵的纵向长度
        int len2 = strTwo.length();
        
        // 保存矩阵的上一行
        int[] topLine = new int[len1];
        // 保存矩阵的当前行
        int[] currentLine = new int[len1];
        // 矩阵元素中的最大值
        int maxLen = 0;
        // 矩阵元素最大值出现在第几列
        int pos = 0;
        char ch = ' ';
        for(int i=0; i<len2; i++){
            ch = strTwo.charAt(i);
            // 遍历str1，填充当前行的数组
            for(int j=0; j<len1; j++){
                if( ch == strOne.charAt(j)){
                    // 如果当前处理的是矩阵的第一列，单独处理，因为其坐上角的元素不存在
                    if(j==0){
                        currentLine[j] = 1;
                    } else{
                        currentLine[j] = topLine[j-1] + 1;
                    }
                    if(currentLine[j] > maxLen){
                        maxLen = currentLine[j];
                        pos = j;
                    }
                }
            }
            // 将矩阵的当前行元素赋值给topLine数组; 并清空currentLine数组
            for(int k=0; k<len1; k++){
                topLine[k] = currentLine[k];
                currentLine[k] = 0;
            }
            // 或者采用下面的方法
            // topLine = currentLine;
            // currentLine = new int[len1];
        }
        return strOne.substring(pos-maxLen+1, pos+1);
    }
    
    public static void main(String[] args) {
        String str1 = "bab";
        String str2 = "caba";
        String result = Solution.maxSubstring(str1, str2);
        System.out.println(result);
    }
}