Kadaneのアルゴリズムでのクエリ

Question

私は、最大サブアレイ問題のためのKadane's Algorithmを行っています。私たちが持っているアルゴリズムから理解できるものは、サブアレイです。サブ配列には配列全体が含まれますか？

実は私はここでは、配列のすべての要素の合計であり、最終的な答えとして13を与えている次のプログラムを

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

をしようとしていました。

Answer 1

はい、連続したサブアレイは、アレイ全体を含む解決策になります。空のサブアレイがあまりにも有効な解決策になるかもしれません

注