题目地址：

https://www.lintcode.com/problem/continuous-subarray-sum-ii/description

给定一个数组$A$，求其最大和子数组的起始和终止下标。这里子数组允许从某个位置出发，到达最右端后回到最左端继续取（当然同一个数字只能取一次）。

对于通常定义的子数组之下，可以用动态规划。设$f[i]$是以$A[i]$结尾的最大和子数组的数字和，则$$f[i]=\max \{f[i-1]+A[i],A[i]\}$$同时用两个变量记一下开始点和结束点即可。如果要求允许跨越边界的最大和子数组，则可以先求一下不跨边界的最小和的子数组，然后再用总和减去之即可。代码如下：

import java.util.ArrayList; import java.util.List; public class Solution { /* * @param A: An integer array * @return: A list of integers includes the index of the first number and the index of the last number */ public List<Integer> continuousSubarraySumII(int[] A) { // write your code here List<Integer> res = new ArrayList<>(); int sum = 0; int start = 0, end = 0; int maxSum = Integer.MIN_VALUE, s = 0, e = 0; int totalSum = 0; for (int i = 0; i < A.length; i++) { totalSum += A[i]; if (sum + A[i] > A[i]) { end = i; sum += A[i]; } else { start = end = i; sum = A[i]; } // 找到了更大的子数组的和，则记录该和，并且记录其起始点和终止点 if (sum > maxSum) { maxSum = sum; s = start; e = end; } } // 求一下最小和子数组 int minSum = totalSum; sum = start = end = 0; for (int i = 0; i < A.length; i++) { if (sum + A[i] < A[i]) { end = i; sum += A[i]; } else { start = end = i; sum = A[i]; } if (sum < minSum) { minSum = sum; // 如果剩余数组和大于之前已经得到的最大和，则更新答案 if (totalSum - minSum > maxSum) { s = end + 1; e = start - 1; } } } res.add(s % A.length); res.add(e % A.length); return res; } }

时间复杂度$O(n)$，空间$O(1)$。