使用 kadane 算法查找最大子数组和的数组

Question

求长度为 N 的数组 Arr 中连续非空子数组及其元素的最大和。

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;
        for(int i = 0 ; i < Arr.size(); i++) {
            currSum = currSum + Arr.get(i);
            maxSum = Math.max(maxSum, currSum);
            if(currSum < 0) currSum = 0;//reset currSum when its negative value
        }
        System.out.print(maxSum);
    }

}

我可以获得子数组总和中的 maxSum，但是，在使用此算法遍历数组时如何存储对 maxSum 有贡献的子数组元素？ 预期输出：4,-1,-2,1,5

Answer 1

您可以跟踪最大和数组的开始和结束索引。遍历完后，可以从主数组创建一个子数组，并在需要的地方使用。

import java.util.ArrayList;
import java.util.Arrays;

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 start = 0, end = 0;

        for (int i = 0; i < Arr.size(); i++) {
            currSum = currSum + Arr.get(i);

            if (currSum > maxSum) {
                maxSum = currSum;
                end = i;
            }

            if (currSum < 0) {
                currSum = 0;
                start = i + 1;
            }
        }

        ArrayList<Integer> subarray = new ArrayList<>(Arr.subList(start, end + 1));
        System.out.println("Max sum sub array: " + subarray);
        final int maxSumValue = subarray.stream().mapToInt(Integer::intValue).sum();
        System.out.println("Max Sum: " + maxSumValue);
    }
}