3466226_ac_5813ms_22640k.java

来自「北大大牛代码 1240道题的原代码 超级权威」· Java 代码 · 共 53 行

import java.util.*;

public class Main {

	private Scanner in;

	private HashMap<LinkedList, Integer> hm;

	public static void main(String[] args) {
		new Main().run();
	}

	private void run() {
		in = new Scanner(System.in);
		int n, k, t, ans;
		int [][] s;
		LinkedList <Integer> al = new LinkedList <Integer> ();

		ans = 0;
		n = in.nextInt();
		k = in.nextInt();
		s = new int [n + 1][k];
		for (int i = 0; i < k; i++) {
			al.addLast(0);
		}
		hm = new HashMap <LinkedList, Integer> ();
		hm.put(al, 0);
		for (int i = 1; i <= n; i++) {
			t = in.nextInt();
			al.clear();
			for (int j = 0; j < k; j++) {
				int tmp = 1 << j;
				if ((tmp & t )!= 0) {
					s[i][j] = s[i - 1][j] + 1;
				} else {
					s[i][j] = s[i - 1][j];
				}
				al.addLast(s[i][j] - s[i][0]);
			}
			if (!hm.containsKey(al)) {
				hm.put(al, i);
			} else {
				int pos = hm.get(al);
				if (i - pos > ans){
					ans = i - pos;
				}
			}
		}
		System.out.println(ans);
	}

}