力ブラシ問題53.最大サブシーケンス和(java)

タイトル
整数配列numsを指定し、最大和を持つ連続サブ配列(サブ配列には少なくとも1つの要素が含まれている)を見つけ、その最大和を返します.
例:
入力:[−2,1,−3,4,−1,2,1,−5,4],出力:6解釈:連続サブ配列[4,−1,2,1]の和が最大で6であった.ステップアップ:複雑度O(n)の解法を実現した場合は、より優れた分治法を用いて解くことを試みます.
解法
最大のサブ配列の和を算出

sumはサブシーケンスの和であり、sum>0は結果が増加したことを示し、sumは現在の遍歴数

を保持する.

sum<=0の場合、sumは結果に対してゲイン効果がないことを示し、捨てる必要がある場合、sumは現在の遍歴数

に直接更新される.

sumとansのサイズを比較するたびに、最大値をansに設定し、ループ終了後に結果

を返す.

時間複雑度O(n)

コード#コード#

class Solution {
    public int maxSubArray(int[] nums) {
        if(nums.length < 1) return 0;
        int sum = 0;
        int ans = nums[0];
        for(int i = 0 ; i < nums.length; i++){
            if(sum > 0) sum += nums[i];
            else sum = nums[i];
            ans = Math.max(ans, sum);
        }

        return ans;
    }
}