毎日1題:LeetCodeの最大サブシーケンスと
整数配列numsを指定し、最大和を持つ連続サブ配列(サブ配列には少なくとも1つの要素が含まれている)を見つけ、その最大和を返します.
例:
入力:[−2,1,−3,4,−1,2,1,−5,4],出力:6解釈:連続サブ配列[4,−1,2,1]の和が最大で6であった.
**構想:**配列を遍歴し、sumで連続サブ配列の和を表し、sumが0より大きい場合、現在の数字の前のいくつかの連続数と0より大きいことを説明し、現在の数字に対して利得がある場合、
例:
入力:[−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;
}