java - 最大和子数组

Question

我试图在具有最大总和的数组中找到连续 子数组。所以，对于数组

{5, 15, -30, 10, -5, 40, 10}

连续使用这些数字的最大总和可能是 55，或 (10 + (-5) + 40 + 10) = 55。下面的程序输出最大总和 55，但是，我想弄清楚的问题是如何打印产生这个 55 的序列。换句话说，我如何打印出 10、-5、40 和 10？

public static void main(String[] args) {
    int[] arr = {5, 15, -30, 10, -5, 40, 10};

    System.out.println(maxSubsequenceSum(arr));         
}

public static int maxSubsequenceSum(int[] X) {
    int max = X[0];
    int sum = X[0];

    for (int i = 1; i < X.length; i++) {
        sum = Math.max(X[i], sum + X[i]);
        max = Math.max(max, sum);
    }
    return max;
}

我正在考虑创建一个 ArrayList 来存储 i 的每个索引处的 sum 值，因此 ArrayList 看起来像 (5, 20, -10, 10, 5, 45, 55) .然后我计划将 ArrayList 从索引 0 清除到列表中的第一个负数，但是，这只能解决这个特定示例的问题，但如果我更改原始数组，则此解决方案将不起作用。

Answer 1

您可以用 if 语句替换 Math.Max 函数，并更新最佳子数组的开始和结束索引。帕斯卡版本:

    if X[i] > sum + X[i] then begin
        sum := X[i];
        start := i;
      end
      else
        sum := sum + X[i];
      if max < sum then begin
        max := sum;
        finish := i;
      end;