LeetCode 解答 #53. Maximum Subarray プログラミング練習

問題：

難易度:　easy
入力:　int[]
目的: 入力されたArrayの中で和が最も大きなSubArrayを求めよ
出力:　int

求めるのはSubArrayなので、入力の中で連続な数字の和を計算していきます。
値が小さくなると言うことは、前の累計がマイナスだったと言うことなので、
そこで分岐すれば行けるはずです。

注意すべき事:　

• maxの値を求めるだけなのでsubArrayを記録する必要はない

以下回答です。

class Solution {
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        int sum = 0;
        int max = Integer.MIN_VALUE;
        for(int i=0; i<len; i++) {
            sum += nums[i];
            if (sum > max) {
                max = sum;
            }
            if (sum < 0) {
                sum = 0;
            }
        }
        return max;
    }
}

forで行列の中を頭から足していき、最大値が更新された場合maxに記録。
累計が0以上であれば続け、マイナスだった場合は破棄して繰り返します。

今日は以上。
よいプログラミング生活を！