所需最大子数组提示

Answer 1

你的问题可以在这里找到参考。

您必须使用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;
}