题解 | #DNA序列#

这道题我的思路是这样的，

先算位置0到n包含多少CG

然后从位置1开始1->n+1 这个要基于0->n这个位置来计算

也就是退0位的字母，增加n+1位置的字母

注意这个继承连续性就能正确调试出来。

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        int n = Integer.parseInt(in.nextLine());
        Node[][] node = new Node[str.length()][str.length()];
        int cNum = 0;
        int gNum = 0;
        int result = -1;
        String strResult = null ;
        for (int i = 0; i < n; i++) {
            Node tt = new Node();
            if (i - 1 >= 0) {

                tt.gNum = node[0][i - 1].gNum;
                tt.cNum = node[0][i - 1].cNum;
            }

            if (str.charAt(i) == 'C') {
                tt.cNum++;
            }
            if (str.charAt(i) == 'G') {
                tt.gNum++;
            }
            node[0][i] = tt;

        }
        result = node[0][ n - 1].cNum + node[0][ n - 1].gNum;
     strResult = str.substring(0,n);

        for (int i = 1; i < str.length(); i++) {
            if ((i + n) < str.length()) {
                Node tt = new Node();
             
                tt.gNum = node[i - 1][i + n - 2].gNum;
                tt.cNum = node[i - 1][i + n - 2].cNum;
                if (str.charAt(i - 1) == 'C') {

                    tt.cNum =  node[i - 1][i + n - 2].cNum - 1;

                }
                if (str.charAt(i - 1) == 'G') {
                    tt.gNum = node[i - 1][i + n - 2].gNum - 1;

                }
                if (str.charAt(i + n - 1) == 'C') {
                    tt.cNum = tt.cNum + 1;


                }
                if (str.charAt(i + n - 1) == 'G') {

                    tt.gNum = tt.gNum + 1;
                }
                node[i][i + n - 1] = tt;
                if (node[i][i + n - 1].cNum + node[i][i + n - 1].gNum > result) {
                    result = node[i][i + n - 1].cNum + node[i][i + n - 1].gNum;
                    strResult = str.substring(i, i + n);
                }
            }


        }
        System.out.println(strResult);


    }

    public static class Node {
        public   int cNum = 0;
        public   int gNum = 0;
    }

}