基于Kadane算法获取最大子数组和及对应子数组元素

你的代码实现了Kadane算法计算最大子数组和，但缺少对产生该和的子数组区间的跟踪。要获取目标子数组4,-1,-2,1,5，我们需要在遍历过程中记录当前子数组的起始索引，以及最大子数组的起止索引，具体修改如下：

需要添加的变量 #

新增三个索引变量来跟踪子数组位置：

• currentStart：标记当前正在累加的子数组的起始位置
• maxStart：记录最大子数组的起始索引
• maxEnd：记录最大子数组的结束索引

修改后的完整代码 #

import java.util.*;

public class MaximumSubarraySum {

    public static void main(String[] args) {
        ArrayList<Integer> Arr = new ArrayList<Integer>(Arrays.asList(-2,-3,4,-1,-2,1,5,-3));
        int currSum = 0, maxSum = Integer.MIN_VALUE;
        // 新增索引变量
        int currentStart = 0;
        int maxStart = 0;
        int maxEnd = 0;

        for(int i = 0 ; i < Arr.size(); i++) {
            // 当前和为0时，说明之前的累加无正向贡献，从当前元素重新开始
            if (currSum == 0) {
                currentStart = i;
            }
            currSum = currSum + Arr.get(i);
            
            // 更新最大和的同时，同步记录对应的子数组起止索引
            if (currSum > maxSum) {
                maxSum = currSum;
                maxStart = currentStart;
                maxEnd = i;
            }
            
            // 当前和为负时重置，后续从下一个元素重新累加
            if(currSum < 0) {
                currSum = 0;
            }
        }
        
        // 输出结果
        System.out.println("最大子数组和：" + maxSum);
        // 注意subList是左闭右开区间，所以结束索引要+1
        List<Integer> maxSubarray = Arr.subList(maxStart, maxEnd + 1);
        System.out.println("最大子数组元素：" + maxSubarray);
    }
}

关键逻辑说明 #

1. 重置当前子数组起点：当currSum为0时，说明之前的累加对后续没有正向帮助，此时将currentStart设为当前索引i，从当前元素开始重新构建子数组。
2. 锁定最大子数组区间：每当currSum超过maxSum时，说明找到了更大的子数组和，立刻更新maxStart和maxEnd为当前子数组的起止索引。
3. 截取子数组：利用ArrayList的subList方法获取目标子数组，由于该方法的结束索引是开区间，所以需要传入maxEnd + 1才能包含最后一个元素。

运行代码后会输出：

最大子数组和：7
最大子数组元素：[4, -1, -2, 1, 5]

内容的提问来源于stack exchange，提问作者HK123