题解 | #DNA序列#

动态规划

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            String str = in.next();
            int len = in.nextInt();
            // 如果长度比字符串长，那数据有问题
            if (len >= str.length()) {
                System.out.println(str);
            } else {
                maxSelect(str, len);
            }
        }
    }

    private static void maxSelect(String str, int len) {
        int[] dq = new int[str.length()];
        boolean[] dq2 = new boolean[str.length()];
        int tmp = 0;
        int max = 0;
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            dq2[i] = (c == 'G' || c == 'C');
            if (i < len) {
                if (c == 'G' || c == 'C') {
                    tmp++;
                }
                dq[i] = tmp;
            } else {
                dq[i] = dq[i - 1] - (dq2[i - len] ? 1 : 0) + (dq2[i] ? 1 : 0);
            }
            max = Math.max(max, dq[i]);
        }
        // 拿到第一个最大值
        int index = 0;
        for (int i = 0; i < dq.length; i++) {
            if (dq[i] == max) {
                index = i;
                break;
            }
        }
        if (index < len) {
            System.out.println(str.substring(0, len));
        }else {
            System.out.println(str.substring(index- len +1,index+1));
        }
    }
}