答案： 不是。并不是所有的正整数都能分解为连续的正整数和，如 32 就不能分解为连续正整数和。对于奇数，我们总是能写成 2k+1 的形式，因此可以分解为 [k,k+1]，所以总是能分解成连续正整数序列。对于每一个偶数，均可以分解为质因数之积，即 n = 2i * 3j * 5k...，如果除了i之外，j，k...均为0，那么 n = 2i，对于这种数，其所有的因数均为偶数，是不存在连续子序列和为 n 的，因此除了2的幂之外的所有 n>=3 的正整数均可以写成一个连续的自然数之和。
5.最大连续子序列和题： 求取数组中最大连续子序列和，例如给定数组为 A = {1， 3， -2， 4， -5}， 则最大连续子序列和为 6，即 1 + 3 +（-2）+ 4 = 6。
分析： 最大连续子序列和问题是个很老的面试题了，最佳的解法是 O(N) 复杂度，当然有些值得注意的地方。这里总结三种常见的解法，重点关注最后一种 O(N) 的解法即可。需要注意的是有些题目中的最大连续子序列和如果为负，则返回0；而本题如果是全为负数，则返回最大的负数即可。
解1： 因为最大连续子序列和只可能从数组 0 到 n-1 中某个位置开始，我们可以遍历 0 到 n-1 个位置，计算由这个位置开始的所有连续子序列和中的最大值。最终求出最大值即可。
/** * 最大连续子序列和 */ int maxSumOfContinuousSequence(int a[], int n) { int max = a[0], i, j, sum; // 初始化最大值为第一个元素 for (i = 0; i < n; i++) { sum = 0; // sum必须清零 for (j = i; j < n; j++) { //从位置i开始计算从i开始的最大连续子序列和的大小，如果大于max，则更新max。 sum += a[j]; if (sum > max) max = sum; } } return max; } 复制代码解2： 该问题还可以通过分治法来求解，最大连续子序列和要么出现在数组左半部分，要么出现在数组右半部分，要么横跨左右两半部分。因此求出这三种情况下的最大值就可以得到最大连续子序列和。
/** * 最大连续子序列和-分治法 */ int maxSumOfContinuousSequenceSub(int a[], int l, int u) { if (l > u) return 0; if (l == u) return a[l]; int m = (l + u) / 2; /*求横跨左右的最大连续子序列左半部分*/ int lmax = a[m], lsum = 0; int i; <span>for</span> (i = m; i >= l; i--) { lsum += a[i]; <span>if</span> (lsum > lmax) lmax = lsum; } /*求横跨左右的最大连续子序列右半部分*/ int rmax=a[m+1], rsum = 0; <span>for</span> (i = m+1; i <= u; i++) { rsum += a[i]; <span>if</span> (rsum > rmax) rmax = rsum; } <span>return</span> max3(lmax+rmax, maxSumOfContinuousSequenceSub(a, l, m), maxSumOfContinuousSequenceSub(a, m+1, u)); //返回三者最大值}
复制代码
解3： 还有一种更好的解法，只需要 O(N) 的时间。因为最大 连续子序列和只可能是以位置 0～n-1 中某个位置结尾。当遍历到第 i 个元素时，判断在它前面的连续子序列和是否大于0，如果大于0，则以位置 i 结尾的最大连续子序列和为元素 i 和前面的连续子序列和相加；否则，则以位置 i 结尾最大连续子序列和为a[i]。
/** * 最打连续子序列和-结束位置法 */ int maxSumOfContinuousSequenceEndIndex(int a[], int n) { int maxSum, maxHere, i; maxSum = maxHere = a[0]; // 初始化最大和为a[0] for (i = 1; i < n; i++) { if (maxHere <= 0) maxHere = a[i]; // 如果前面位置最大连续子序列和小于等于0，则以当前位置i结尾的最大连续子序列和为a[i] else maxHere += a[i]; // 如果前面位置最大连续子序列和大于0，则以当前位置i结尾的最大连续子序列和为它们两者之和 if (maxHere > maxSum) { maxSum = maxHere; //更新最大连续子序列和 } } return maxSum; } 复制代码6.最大连续子序列乘积题： 给定一个整数序列（可能有正数，0和负数），求它的一个最大连续子序列乘积。比如给定数组a[] = {3, -4, -5, 6, -2}，则最大连续子序列乘积为 360，即 3*(-4)*(-5)*6=360。
解： 求最大连续子序列乘积与最大连续子序列和问题有所不同，因为其中有正有负还有可能有0，可以直接利用动归来求解，考虑到可能存在负数的情况，我们用 max[i] 来表示以 a[i] 结尾的最大连续子序列的乘积值，用 min[i] 表示以 a[i] 结尾的最小的连续子序列的乘积值，那么状态转移方程为：
max[i] = max{a[i], max[i-1]*a[i], min[i-1]*a[i]}; min[i] = min{a[i], max[i-1]*a[i], min[i-1]*a[i]}; 复制代码