今晚被这道题折磨了好久，记录下。

题意

对数组的子序列（任意相连的元素）求和，找出所有和里对M的模中的最大值。

思路

开始就想到能不能按照“最大子序列和问题”的思路解决，后来发现无论是分治递归求解还是复杂度为O(N)的算法在这个问题中都没有用，于是看了题解。
在Quora上找到了题解，看了半天才看明白。大意是，对于输入的数组v中的元素v[i]，先找到v[i]之前所有数的和对M取模的值（包括v[i]），存到数组prefix中。这里有个技巧，

1
2
3
4
5
6

ull tmp = 0;  // unsigned long long
for (size_t i=0; i<v_size; ++i) {
    tmp += v[i];
    tmp %= m;
    prefix.push_back(tmp);
}