最大总和子阵列

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来存储sumi的每个索引处的值,因此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;

Answer 2

您可以跟踪循环中当前最佳子数组的开始和结束索引。不要使用max()来计算sum和max，只需执行以下操作：

int sum_start = 0, sum_end = 0, start = 0, end = 0;
// In the for loop
if (X[i] > sum + X[i]) {
    sum = X[i];
    sum_start = i;
    sum_end = i;
} else {
    ++sum_end;
}
if (sum > max) {
    start = sum_start;
    end = sum_end;
    max = sum;
}