説明#
整数配列 nums が与えられた場合、最大の和を持つ連続した部分配列（部分配列には少なくとも 1 つの要素が含まれる）を見つけ、その最大和を返します。
例:
入力: [-2,1,-3,4,-1,2,1,-5,4],
出力: 6
説明: 連続した部分配列 [4,-1,2,1] の和が最大であり、その値は6です。
高度な問題:
O(n) の解法をすでに実装している場合、より洗練された分割統治法を使用して解を求めてみてください。
アプローチ#
- 配列全体の最大要素を見つけ、0 以下の場合はその数を直接返します。
- 最大要素が 0 より大きい場合、最大部分和も必ず 0 より大きいことがわかります。配列の数を走査し、正の数は部分配列の最初の要素として後ろに加算して和を計算します。和が 0 以下の場合は新しい部分配列を探し、和が最大値を超える場合は更新します。
int maxSubArray(int* nums, int numsSize){
int now_val = 0,max_val = nums[0];
for(int i=0;i<numsSize;i++)//最大の要素を見つける
if(nums[i] > max_val)
max_val = nums[i];
if(max_val <= 0)//最大要素が0以下の場合はそのまま返す
return max_val;
//max_valが0より大きいことが確定している
for(int i=0;i<numsSize-1;i++) {
if(nums[i] > 0) {
for(int j=i+1,now_val=nums[i];j<numsSize;j++) {
now_val += nums[j];
if(now_val <= 0)
break;
if(now_val > max_val)
max_val = now_val;
}
}
}
return max_val;
}