毎日1題:LeetCodeの最大サブシーケンスと

2942 ワード

整数配列numsを指定し、最大和を持つ連続サブ配列(サブ配列には少なくとも1つの要素が含まれている)を見つけ、その最大和を返します.
例:
入力:[−2,1,−3,4,−1,2,1,−5,4],出力:6解釈:連続サブ配列[4,−1,2,1]の和が最大で6であった.
**構想:**配列を遍歴し、sumで連続サブ配列の和を表し、sumが0より大きい場合、現在の数字の前のいくつかの連続数と0より大きいことを説明し、現在の数字に対して利得がある場合、sum+=nums[i]、0より小さい場合、前のいくつかの数の和は0より小さい場合、現在の数字に対して利得がないことを説明し、sum=Math.max(sum,nums[i])、resでその中の最大のsumを保存する.
 public int maxSubArray(int[] nums) {
        int sum=0,res=nums[0];

        for(int i=0;i<nums.length;i++){
            if(sum<0)
                sum=Math.max(sum,nums[i]);
            else
                sum+=nums[i];

            res=Math.max(res,sum);
        }
        return res;
    }