需要的最大子數組提示

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; 
}