アルゴリズム解釈[カデイン]

カデイン

[1,-3,-1,2]と同じ数の羅列"数列"があると仮定した時、

各数を加えた時に最も大きな数が出る連続した部分を探すアルゴリズムをカデインアルゴリズムという。

数列アルゴリズムの基礎に該当する問題で

解釈の核心は、

1. 要素を一つずつ足す

2. 「加えた値を変数に保存」

3. 加えた値がその最後に保存しておいた変数値より大きければ変数を代入

JavaCodeで見ると、

int[] nums = {1,-3, -1, 2}; 
public static int maxSubArray(int[] nums) { 
     //配列の長さが1の場合は加えることがないので0番地のまま返却 
     if(nums.length == 1) { return nums[0]; } 
     //該当osのint範囲での最小値を初期値に設定、各配列要素の合算値
     int maxValInt = Integer.MIN_VALUE, sumVal = 0; 
     //1.配列要素を一つずつ回転しながら価格を足してみる(最大部分和を求めるために) 
     for(int i = 0, j = nums.length; i < j; i++) { 
         //2.合算値代入 
         sumVal += nums[i]; 
         //3.以前の合算保存値と比較して、より大きな値であれば置
         if (maxValInt < sumVal) maxValInt = sumVal; 
         if (sumVal < 0) sumVal = 0; 
      } 
      return maxValInt; 
}