Java中的最大子序列和算法

Question

我有一个整数数组，我想找到最大子序列和（MSS）。我试图递归地解决这个问题——使用分而治之的方法

想法是将数组分成两半，在两半上递归，然后找到数组左右两半的最大和，然后将它们与我从递归中得到的值进行比较

我知道还有其他方法可以解决这个问题。但是，我想先找出代码中的错误，然后再看其他解决方案。现在，通过我的输入，我得到的MSS是12，它应该是8（2，5，-5，5，1）

import java.lang.Math;

public class Solution {
  public static void main(String[] args){
    int[] arr = new int[7];    
    arr[0] = 1;
    arr[1] = -3;
    arr[2] = 2;
    arr[3] = 5;
    arr[4] = -5;
    arr[5] = 5;
    arr[6] = 1;
    System.out.println(helper(arr, 0, arr.length - 1));
  }

  public static int helper(int[] arr, int low, int high) {
    if (low >= high) {
        return Math.max(arr[low], 0);
    }

    int mid = low + (high - low) / 2;
    int L = helper(arr, low, mid);
    int R = helper(arr, mid + 1, high);

    int sum = 0;
    int leftSum = 0;

    for (int i = mid - 1; i >= 0; i--) {
        sum = sum + arr[i];
        leftSum = Math.max(leftSum, sum);
    }

    sum = 0;
    int rightSum = 0;

    for (int i = high; i >= mid; i--) {
        sum = sum + arr[i];
        rightSum = Math.max(rightSum, sum);
    }

    return Math.max(L, Math.max(R, leftSum + rightSum));
  }
}

我到底错在哪里

编辑：我试图找到最大连续和

Answer 1

• 首先，我在你的程序中没有看到任何递归的用法
• 其次，您的解决方案是O(2*n)，并且当前是错误的

此解决方案可以通过O(n)实现，如下所示：

import java.lang.Math;

public class Solution {
    public static void main(String[] args){
        int[] arr = {1, -3, 2, 5, -5, 5, 1};
        System.out.println(maximumSubsequenceSum(arr));
    }

    public static int maximumSubsequenceSum(int[] arr) {
        int maxSoFar = 0;
        int maxEndingHere = 0;
        for(int item : arr) {
            maxEndingHere = Math.max(maxEndingHere + item, 0);
            maxSoFar = Math.max(maxSoFar, maxEndingHere);
        }
        return maxSoFar;
    }
}

此解决方案完全基于本文中描述的算法：Solving the maximum subsequence sum and related problems using BSP/CGM model and multi-GPU CUDA