java - 需要最大子数组提示

Question

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray [4,-1,2,1] has the largest sum = 6.

我无法解决这个问题，但我只是想得到一些提示。

它说这可以使用动态规划来解决，但我很难看到其中的联系。

DP 连接会获取整个 数组的总和吗？

Answer 1

可以找到您的问题的引用 here .

你必须使用 Kadane 的算法来解决这种情况，它是这样的:

Initialize:
    max_so_far = 0
    max_ending_here = 0

Loop for each element of the array
    (a) max_ending_here = max_ending_here + a[i]
    (b) if(max_ending_here < 0)
        max_ending_here = 0
    (c) if(max_so_far < max_ending_here)
        max_so_far = max_ending_here
    return max_so_far

供您引用的示例代码:

static int maxSubArraySum(int a[])
{
    int size = a.length;
    int max_so_far = Integer.MIN_VALUE, max_ending_here = 0;

    for (int i = 0; i < size; i++)
    {
        max_ending_here = max_ending_here + a[i];
        if (max_so_far < max_ending_here)
            max_so_far = max_ending_here;
        if (max_ending_here < 0)
            max_ending_here = 0;
    }
    return max_so_far;
}