晚上参加美团的笔试，今天从坐了一天的车，到了学校匆忙吃了饭，然后就开始了。确实是，脑子有点不灵光。
编程的第一题： 给定一个序列，输出这个序列子串的和为K的倍数的子串的长度，如果有重复，输出最大长度。 例如：序列为：{1,2,3,4,5} k = 5 那么子串的和为5的倍数的有{2,3}，{1,2,3,4}，{1,2,3,4,5},{5} ，而这时长度最大的是5，所以输出5。
刚开始看到这道题，我的脑子里第一反应是：不能去暴力列出所有可能，一定会超时！
然后脑子也就停在这里了。知道要用动态规划的原理去做，因为当前状态与上一个状态息息相关。可是我一直往左右指针的方向去想，结果时间就到了。
洗了个澡，重新思考这个题目，发现其实超级简单。
每一个子串都可以看做上一个子串减去第一个。然后用一个二维数组记录每一个子串的和，就解决了这个问题。
import java.util.Scanner; public class Main { static int[] a = null; static int k = 0; static int max = 0; public static void main(String[] args) { Scanner s = new Scanner(System.in); s.nextLine(); String[] c = s.nextLine().split(" "); a = new int[c.length]; for (int i = 0; i < c.length; i++) { a[i] = Integer.valueOf(c[i]); } k = Integer.valueOf(s.nextLine()); // Random random = new Random(); // a = new int[10 * 1000]; // for (int i = 0; i < 10 * 1000; i++) { // a[i] = random.nextInt(500000); // } // // k = 20000; int[] dp = new int[a.length + 1]; for (int i = 0; i < a.length; i++) { dp[0] = 0; for (int j = i; j < a.length; j++) { dp[j + 1] = dp[j] + a[j]; if (dp[j + 1] % k == 0) { if (max < j - i+1) { max = j - i+1; } } } } System.out.println(max); } }