int array[] = {-1, 4, -2, 5, -5, 2, -20, 6};
如果我有這樣的陣列，我Kadane算法實現以找到最大的子陣列的工作原理：Kadane算法負數
int max_so_far = INT_MIN;
int max_ending_here = 0;
for (int i = 0; i < size; i++) {
max_ending_here = max(max_ending_here + array[i], 0);
max_so_far = max(max_ending_here, max_so_far);
}
printf("%d\n", max_so_far);
但是，如果我把所有的底片的數組：
int array[]= {-10, -10, -10};
它不會工作，它應該返回-10，但我得到0.
我怎樣才能使它的負數呢？
謝謝！
根據Wikipedia，Kadane的算法需要至少一個正數，所以你所有的負數組是無效輸入。
當所有的元素都是負的，最大子數組是空的子陣列，它具有和0
但是，如果你想改變算法的最大元素存儲在這種情況下，你可以做到以下幾點：
int max_so_far = INT_MIN;
int max_ending_here = 0;
int max_element = INT_MIN;
for (int i = 0; i < size; i++)
{
max_ending_here = max(max_ending_here + array[i], 0);
max_so_far = max(max_ending_here, max_so_far);
max_element = max(max_element, array[i]);
}
if (max_so_far == 0)
max_so_far = max_element;
printf("%d\n", max_so_far);
如果所有元素均爲負數，則返回負數最小的數字。 在其他所有情況下，您的解決方案都可以正常工作。
printf("%d\n",max(max_so_far, *max_element(array,array+size)));
int max_so_far = INT_MIN;
int max_ending_here = array[0];
for (int i = 1; i < size; i++) {
max_ending_here = max(max_ending_here + array[i], array[i]);
max_so_far = max(max_ending_here, max_so_far);
}
printf("%d\n", max_so_far);
它可以工作
稍作除了Kadane的算法中。 在遍歷數組的同時，獲取一個標誌are_all_elements_negative（設置爲true）和一個int（存儲最高的整數） ，如果找到一個正數，則將該標誌設置爲false。 標誌爲true時，存儲最高數量。最後，檢查標誌，如果標誌爲true，則輸出-ve整數，否則輸出常規Kadane的算法輸出。
那麼當數組中的所有元素都是負數時，Kadane算法不適用於這種情況。在這種情況下，它只返回0。如果您想要處理這個問題，我們需要在實際實施之前添加額外的階段。如果所有數字都是負數，那麼階段將會顯示，如果它們將返回最大值（或絕對值最小）。
我可以建議一個實現
#define find_max_val(x,y) x >= y ?x :y;
int min_sum(int a[],int n){
int min_so_far = a[0],min_end_here = a[0];
for(int i = 1;i < n; i++){
min_end_here = find_max_val(a[i],min_end_here + a[i]);
min_so_far = find_max_val(min_so_far,min_end_here);
}
return min_so_far;
}
仍有取決於那些需要其他實現。
我遲到了這次派對，但會有這樣的工作嗎？：
cur_sum = max_sum = sequence[0];
sum_to_j = 0;
for j in range(0, len(sequence)):
sum_to_j += sequence[j];
if sum_to_j > cur_sum:
cur_sum = sum_to_j;
if cur_sum > max_sum:
max_sum = cur_sum
if sum_to_j < 0:
sum_to_j = 0;
cur_sum = sequence[j];
print max_sum;
我認爲，以下將工作： -
int maxSub(vector<int> x){
int sum=x[0],local_max=0;
for(int i=0;i<x.size();i++){
local_max+=x[i];
if(sum < local_max)
sum=local_max;
if(local_max <0)
local_max=0;
}
return sum;
}
如果所有元素都是負面的，由價值
boolean allNegative = true;
int bigNegative = Integer.MIN_VALUE;
int maxSum = 0;
int sum = 0;
for(int i=0;i<a.size();i++){
// if all numbers are negative
if(a.get(i)>=0){
allNegative = false;
}else{
if(a.get(i)>bigNegative){
bigNegative = a.get(i);
}
}
sum += a.get(i);
if(sum<0){
sum=0;
}
if(sum>maxSum){
maxSum = sum;
}
}
if(allNegative){
return bigNegative;
}
return maxSum;
它與返回的最大元素下面的代碼。
public int algorithmKadane(int[] input_array){
int sum = input_array[0];
int rotate_sum = input_array[0];
for(int i=1; i< input_array.length ; i++){
rotate_sum = Math.max(input_array[i], rotate_sum+input_array[i]);
sum = Math.max(rotate_sum,sum);
}
return sum;
}
請參考wikiped kadane算法max subarray
int max_subArray(Integer[] input){
int max_so_far,max_ending_here;
max_so_far = max_ending_here =input[0];
for(int i =1; i<input.length;i++){
max_ending_here = Math.max(input[i], input[i]+max_ending_here);
max_so_far = Math.max(max_so_far, max_ending_here);
}
return max_so_far;
}
，它將返回-10你的情況
也許你可以擴大爲什麼/如何這個解決方案會工作，並請評論你碼。 – 2013-07-12 02:54:25
最重要的是，您應該檢查數組是否爲空或空。將max_ending_here的值設置爲數組值的第一個數字。然後從數組的第二個數字開始循環數組，如果選擇（max_ending_here + array [i]，array [i]）的最大值。如果數組都是負數，則輸出將是最大的負數。 – flmAtVancl 2013-07-12 06:17:16