给定一个整数数组，要求找出一个连续子序列，使得该子序列中所有元素的和最大，同时还需要输出这个子序列的起点、终点以及长度信息。这个需求看似只是对经典最大子数组和问题的小扩展，但在实际工程中却有着明确的场景，比如在股票价格序列中寻找最大涨幅区间，或者在一段传感器数据中定位收益最高的连续时间段。如果只返回最大和，很多后续分析便无法开展。
问题定义如下：输入一个整型数组 nums，其中元素可正可负可为零。定义子序列为数组中下标连续的一段。任务是要找到一个下标对 i 和 j（满足 0 ≤ i ≤ j < nums.length），使得 sum = nums[i] + ... + nums[j] 达到最大值。如果存在多个这样的区间，则根据“兼顾长度”的规则，要么选择长度最短的区间，要么选择长度最长的区间，依具体需求而定。本文会分别讨论这两种规则下的实现。
暴力枚举与朴素优化
最直观的解法是三重循环：枚举起点 i，枚举终点 j，然后在内层再循环累加 i 到 j 之间的元素得到子序列和。这种方法的时间复杂度为 O(n³)，空间复杂度为 O(1)。虽然简单易懂，但当数组长度超过几百时性能会严重下降，不适合实际使用。
一个简单的改进是预先计算前缀和数组 prefix，其中 prefix[k] 表示前 k 个元素的和（prefix[0] = 0）。那么任意区间 [i, j] 的和就可以用 prefix[j+1] - prefix[i] 在 O(1) 时间内得到。这样枚举起点和终点只需要两重循环，总时间复杂度降为 O(n²)。代码如下所示：
public int[] bruteForceWithPrefix(int[] nums) {
int n = nums.length;
int[] prefix = new int[n + 1];
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
int maxSum = Integer.MIN_VALUE;
int start = 0, end = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
int sum = prefix[j + 1] - prefix[i];
if (sum > maxSum) {
maxSum = sum;
start = i;
end = j;
}
}
}
return new int[]{maxSum, start, end, end - start + 1};
}
这个版本已经可以返回最大和以及对应的起止下标和长度。但如果数组中存在多个相同的最大和，这段代码只会记录第一次遇到的区间，因为使用的是严格大于号。若想改为选择长度最短或最长的区间，就需要在条件中增加额外的判断逻辑，比如当 sum == maxSum 时比较当前区间长度和已有区间的长度，并按照规则更新。这在设计时稍加注意即可。
Kadane算法的核心与索引追踪
暴力枚举虽然直观，但 O(n²) 的时间复杂度在面对百万级数据时依然乏力。1977年由Joseph Kadane提出的动态规划思想可以把复杂度降到 O(n)。其核心在于：对于每个位置 i，考虑以 i 结尾的最大子序列和。如果前一个位置 i-1 结尾的最大子序列和是正数，那么加上当前元素后总和会更大；如果是负数或零，则不如从当前元素重新开始。所以状态转移方程为：currentMax = Math.max(nums[i], currentMax + nums[i])。整体最大和就是所有 currentMax 中的最大值。
这个算法有一个微妙之处：它天然地得到了以某个位置结尾的最大和，但并没有直接告诉我们区间的起点。为了同时追踪起止下标，需要额外记录一个潜在起点。当 currentMax + nums[i] < nums[i] 时，说明以 i 开始的新子序列比延续之前更优，此时将潜在起点设为 i。否则潜在起点保持不变。当更新全局最大值时，就分别把起点和终点记录下来。下面是一个基础实现：
public int[] kadaneWithIndices(int[] nums) {
int maxSum = Integer.MIN_VALUE;
int currentSum = 0;
int start = 0, end = 0, tempStart = 0;
for (int i = 0; i < nums.length; i++) {
if (currentSum > 0) {
currentSum += nums[i];
} else {
currentSum = nums[i];
tempStart = i;
}
if (currentSum > maxSum) {
maxSum = currentSum;
start = tempStart;
end = i;
}
}
return new int[]{maxSum, start, end, end - start + 1};
}
这段代码在逻辑上等价于比较 currentMax + nums[i] 和 nums[i]，但使用了更简洁的条件判断。需要注意的是，当 currentSum 等于 0 时，我们选择了重新开始，这通常符合“较短子序列优先”的策略，因为如果当前累加和为 0，那么舍弃前面的序列不会改变最大和，但可以让起点更靠后，从而缩短长度。如果不希望这种偏好，可以将条件改为 currentSum >= 0，这样会倾向于延续已有的区间，得到较长的子序列。
并列最大和的长度处理策略
当数组中存在多个子序列拥有相同的最大和时，不同的业务场景可能需要不同的长度取向。例如在信号处理中，可能希望找到尽可能短的尖峰区间，以精确定位异常；而在某些累积收益分析中，则希望找到尽可能长的稳定收益段。Kadane算法的标准实现一旦遇到严格更大的和才会更新起点和终点，这意味着默认返回的是第一个遇到的最大和区间。如果要实现长度优先，需要对更新条件做进一步细化。
以“最短长度优先”为例，当 currentSum == maxSum 时，需要比较当前潜在区间的长度与已记录区间的长度。如果当前区间更短，则更新起点和终点。但这里有一个陷阱：在遍历过程中，潜在起点 tempStart 可能尚未固定，因为当前 currentSum 对应的区间可能在未来还会扩展。因此，当遇到相等和的情况时，不能直接使用 tempStart 作为起点，而需要从 tempStart 到当前位置的长度来比较。一个可行的做法是在每次得到 currentSum 后，记录其对应的起点，并在需要比较时使用该起点计算长度。下面给出一个处理最短长度的版本：
public int[] kadaneShortestMaxSubarray(int[] nums) {
if (nums == null || nums.length == 0) return new int[]{0, -1, -1, 0};
int maxSum = nums[0];
int currentSum = nums[0];
int start = 0, end = 0, tempStart = 0;
for (int i = 1; i < nums.length; i++) {
if (currentSum > 0) {
currentSum += nums[i];
} else {
currentSum = nums[i];
tempStart = i;
}
int currentLength = i - tempStart + 1;
if (currentSum > maxSum ||
(currentSum == maxSum && currentLength < (end - start + 1))) {
maxSum = currentSum;
start = tempStart;
end = i;
}
}
return new int[]{maxSum, start, end, end - start + 1};
}
注意这个版本只适用于最短优先。如果要实现最长优先，只需把长度比较中的小于号换成大于号即可。但需要警惕一种边界情况：当数组全为负数时，最大和就是最大的那个单个元素。按照最短优先，应该返回那个元素本身，长度为 1，上面的代码也能正确处理，因为初始时 currentSum 和 maxSum 都设为第一个元素，后续不会出现相等和且更短的情况，所以返回第一个最大负数所在的单个元素。若需要返回最后出现的那个最大负数，则需要对初始化和比较条件做微调。
完整测试与边界情形讨论
为了验证上述实现，我们编写一个包含典型测试用例的Java主类。测试数组包括：常规混合正负数、全负数、全正数、包含零、多个并列最大和等。同时对比暴力枚举和Kadane算法的结果，确保一致性。以下是完整代码：
public class MaxSubarrayDemo {
public static int[] bruteForce(int[] nums) {
int n = nums.length;
int maxSum = Integer.MIN_VALUE;
int start = 0, end = 0;
for (int i = 0; i < n; i++) {
int sum = 0;
for (int j = i; j < n; j++) {
sum += nums[j];
if (sum > maxSum) {
maxSum = sum;
start = i;
end = j;
}
}
}
return new int[]{maxSum, start, end, end - start + 1};
}
public static int[] kadaneShortest(int[] nums) {
if (nums == null || nums.length == 0) return new int[]{0, -1, -1, 0};
int maxSum = nums[0];
int currentSum = nums[0];
int start = 0, end = 0, tempStart = 0;
for (int i = 1; i < nums.length; i++) {
if (currentSum > 0) {
currentSum += nums[i];
} else {
currentSum = nums[i];
tempStart = i;
}
int curLen = i - tempStart + 1;
if (currentSum > maxSum ||
(currentSum == maxSum && curLen < (end - start + 1))) {
maxSum = currentSum;
start = tempStart;
end = i;
}
}
return new int[]{maxSum, start, end, end - start + 1};
}
public static void main(String[] args) {
int[][] tests = {
{-2, 1, -3, 4, -1, 2, 1, -5, 4},
{-1, -2, -3, -4},
{1, 2, 3, 4, 5},
{0, 0, 0, 0},
{5, -1, 2, 5, -1, 2, 5}
};
for (int[] arr : tests) {
int[] bf = bruteForce(arr);
int[] ks = kadaneShortest(arr);
System.out.printf("Array: %s%n", java.util.Arrays.toString(arr));
System.out.printf(" BruteForce -> sum=%d, start=%d, end=%d, len=%d%n", bf[0], bf[1], bf[2], bf[3]);
System.out.printf(" KadaneShort-> sum=%d, start=%d, end=%d, len=%d%n%n", ks[0], ks[1], ks[2], ks[3]);
}
}
}
运行上述代码后，可以看到对于第一个数组 [-2,1,-3,4,-1,2,1,-5,4]，最大和为 6，对应子序列为 [4,-1,2,1]，起点 3 终点 6，长度 4。对于全负数数组，最大和是 -1，最短长度为 1，返回第一个 -1。对于全正数，最大和为整个数组之和。对于全零数组，最大和为 0，最短长度优先会返回第一个单独的元素 0（长度 1）。对于包含重复最大和的数组 [5,-1,2,5,-1,2,5]，最大和为 16，但存在多个子序列：整个数组和为 16，子序列 [5,-1,2,5,-1,2,5] 长度为 7；此外前缀 [5,-1,2,5,-1,2] 和为 13，并不是最大，所以只有一个区间。这个例子可能不太典型，可以自行构造更明显的并列情况来测试长度选择逻辑。
除了上述实现，还需要注意几个边界：空数组应返回特殊值或抛出异常；数组长度为 1 时直接返回该元素；当最大和为 0 且数组包含正数和负数时，可能没有任何正和区间，此时的最大和非负，需要确保起点和终点有效指向某个零元素或负数中的最大值。在实际工程中，这些边界都应该被显式处理，并编写相应的单元测试。