一般思路：把当前数作为子数组的最后一个数

给定一个数组arr，和一个整数num，求在arr中，累加和等于num的最长子数组的长度

例子：
arr = {7,3,2,1,1,7,7,7} num = 7
其中有很多的子数组累加和等于7，但是最长的子数组是{3,2,1,1}，所
以返回其长度4

思路：按住一个位置，找到以这个位置结尾的最长子数组。
用map记录从位置0开始的累加和与该累加和第一次出现的位置，那么当遍历到一个位置时，只要在map中找是否有 sum-num，如果有的话就是从map.get(sum-num)到该位置的长度。
举例：当遍历到1000时，从0到1000的累加和为2000，如果我们要找800这个累加和，那么只要找到1200第一次出现的位置x，那么x~1000的子数组累加和就是800。

public static int maxLength(int[] arr, int k) {
    if (arr == null || arr.length == 0) {
        return 0;
    }
    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    map.put(0, -1); // important
    int len = 0;
    int sum = 0;
    for (int i = 0; i < arr.length; i++) {
        sum += arr[i];
        if (map.containsKey(sum - k)) {
            len = Math.max(i - map.get(sum - k), len);
        }
        if (!map.containsKey(sum)) {
            map.put(sum, i);
        }
    }
    return len;
}

定义数组的异或和的概念：

数组中所有的数异或起来，得到的结果叫做数组的异或和，
比如数组{3,2,1}的异或和是，3²1 = 0
给定一个数组arr，你可以任意把arr分成很多不相容的子数组，你的目的是：
分出来的子数组中，异或和为0的子数组最多。
请返回：分出来的子数组中，异或和为0的子数组最多是多少？

思路：dp，用map记录异或和为sum的最晚出现的位置k，那么如果0_{i的异或和为sum，则k}i的异或和为0（sum^0=sum）
dp[i]=dp[i-1] (以i为末尾不是异或和为0的子数组)
dp[i] =dp[k-1]+1
取其中较大的值

public static int mostEOR(int[] arr) {
    int ans = 0;
    int xor = 0;
    int[] mosts = new int[arr.length];
    HashMap<Integer, Integer> map = new HashMap<>();
    map.put(0, -1);
    for (int i = 0; i < arr.length; i++) {
        xor ^= arr[i];
        if (map.containsKey(xor)) {
            int pre = map.get(xor);
            mosts[i] = pre == -1 ? 1 : (mosts[pre] + 1);
        }
        if (i > 0) {
            mosts[i] = Math.max(mosts[i - 1], mosts[i]);
        }
        map.put(xor, i);
        ans = Math.max(ans, mosts[i]);
    }
    return ans;
}