需要的最大子数组提示

Question

查找具有最大总和的数组中的连续子数组（至少包含一个 数字）。

例如，给定数组[-2,1，-3,4，-1,2,1，-5,4]，连续的 子数组[4，-1,2,1]具有最大的总和= 6.

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

它说这可以使用动态规划解决，但我很努力地看到一个连接。

DP连接将采用整个数组的总和吗？

Answer 1

max; 
max_ele; 
for (i=0; i< i++) { 
    if (i ==0) { 
    max_ele = i; 
    max =a[i]; 

} else if (max < max + a[i]) { 
    max - max + a[i]; 
    max_ele = i; 
} else { 
    max = 0; 
} 
} 

you get max_ele after this iteration, trace back till negative element or first element to get max. 

Answer 2

您的问题的参考可以找到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; 
}