30.連続サブ配列の最大和

『剣指Offer』ブラシ問題GitHubリンク
タイトルリンク

タイトルの説明

HZはたまに専門的な問題を持って非コンピュータ専門の同級生をからかっている.今日のテストグループの会議が終わった後、彼はまた話をしました:古い1次元モードの識別の中で、いつも連続するサブベクトルの最大和を計算する必要があって、ベクトルがすべて正数の時、問題はとてもよく解決します.しかし、ベクトルに負の数が含まれている場合、ある負の数を含んで、隣の正の数が補うことを期待しますか?
例えば,{6,−3,−2,7,−15,1,2,2},連続サブベクトルの最大和は8(0番目から3番目まで)である.配列をあげて、その最大連続サブシーケンスの和を返して、あなたは彼にだまされませんか?(サブベクトルの長さは少なくとも1)

問題を解く構想.

は、2つの変数、1つのレコードの現在の和、1つのレコードの最大和を使用します.

現在および正の場合、常に新しい数が加えられる.

現在の変数が負の場合、更新現在の変数は次の数になります.

は最大値と比較し、最大値より大きい場合は最大値を更新する.

Code

function FindGreatestSumOfSubArray(array)
{
    // write code here
    var len = array.length;
    var maxSum = array[0],currSum = array[0];
    
    for(var i = 1; i < len; i++){
        if(currSum < 0){
            currSum = array[i];
        }else{
            currSum += array[i];
        }
        if(currSum > maxSum){
            maxSum = currSum;
        }
    }
    return maxSum;
}