三个无重叠子数组的最大和

三个无重叠子数组的和

class Solution {
    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        //通过dp的方式输出
        int n=nums.length;

        //前缀和
        int[] prefix=new int[n+1];
        for(int i=1;i<=n;i++){
            prefix[i]=prefix[i-1]+nums[i-1];
        }

        int[][] dp=new int[n+2][4];//dp[i][j]表示i开始后面的数组元素，划分不重叠的j组元素，最大和为dp[i][j]
        int x=n+1;
        for(int i=n-k+1;i>0;i--){
            for(int j=1;j<=3;j++){
                dp[i][j]=Math.max(dp[i+1][j],dp[i+k][j-1]+prefix[i+k-1]-prefix[i-1]);
            }
            if(dp[i][3]>=dp[x][3]){//将最大的位置记录下来
                  x=i;  
            }
        }
        int index=0;
        int[] res=new int[3];
        for(int j=3;j>=1;j--){
            while(dp[x][j]!=dp[x+k][j-1]+prefix[x+k-1]-prefix[x-1]){x++;}
            res[index++]=x-1;
            x+=k;
        }
        return res;
    }
}

输出最长公共子序列

输出最长公共子序列

 class Solution {
    public String shortestCommonSupersequence(String str1, String str2) {
        int n=str1.length();int m=str2.length();
        int[][] dp=new int[n+1][m+1];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(str1.charAt(i-1)==str2.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else{
                    dp[i][j]=Math.max(dp[i][j-1],dp[i-1][j]);
                }
            }
        }

        //将最长公共子序列输出
        // StringBuilder s=new StringBuilder();
        // int start=n;int end=m;
        // while(dp[start][end]>0){
        //     if(str1.charAt(start-1)==str2.charAt(end-1)){
        //         s.append(str1.charAt(start-1));
        //         start--;end--;
        //     }else{
        //         if(dp[start][end-1]>=dp[start-1][end]){
        //             end--;
        //         }else{
        //             start--;
        //         }
        //     }
        // }

        // s.reverse();
        // System.out.println(s.toString());

        StringBuilder sb=new StringBuilder();
        int i=n;int j=m;
        while(dp[i][j]>0){
            if(str1.charAt(i-1)==str2.charAt(j-1)){
                sb.append(str1.charAt(i-1));
                i--;j--;
            }else{
                if(dp[i-1][j]>=dp[i][j-1]){
                    sb.append(str1.charAt(i-1));
                    i--;
                }else{
                    sb.append(str2.charAt(j-1));
                    j--;
                }
            }
        }

        for(int k=i;k>0;k--){
            sb.append(str1.charAt(k-1));
        }
        for(int k=j;k>0;k--){
            sb.append(str2.charAt(k-1));
        }
        sb.reverse();
        return sb.toString();
    }
}