查詢Kadane的算法

我正在通過Kadane的最大子陣列問題的算法。現在我從聲明中瞭解算法，我們已經找到子數組。子數組是否包含整個數組本身。查詢Kadane的算法

其實我是想下面的程序

int main(void) 
    { 
    int arr[9]={5,6,-4,-1,-2,1,5,3}; 

    int i,n,max_last =0,max_mid =0; 

    for(i=0;i<8;i++) 
    { 
     max_mid = max_mid + arr[i]; 
     printf("max_mid =%d\n",max_mid); 

     if (max_mid < 0) 
       max_mid =0; 

     if(max_mid > max_last) 
       max_last = max_mid; 
    } 

     printf("val=%d",max_last); 
     return 0; 
    }

這是給13作爲最終的答案是陣列的所有元素的總和。

來源

2016-06-15 Abhinav

是的，任何連續的子陣列都可能是一個解決方案，包括整個陣列。

需要注意的是空的子陣可能是有效的解決方案過於（對所有負數算法給出最大總和結果0）

來源

2016-06-15 12:16:31 MBo

+1。這與數學家如何說一整套是其本身的一個子集完全一樣。一個嚴格較小的子集稱爲*合適的子集*，所以我想我們可以使用「合適的子數組」來引用一個不是整個數組的子數組。 – AakashM

我認爲沒有必要爲「合適的子陣列」分離解決方案，因爲算法是針對一般情況的，沒有人聲明這一要求。 – MBo

查詢Kadane的算法

回答

相關問題