Maximum Subarray
2199 ワード
質問する
Given an integer array nums , find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
A subarray is a contiguous part of an array.Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Example 2:
Input: nums = [1]
Output: 1
Example 3:
Input: nums = [5,4,-1,7,8]
Output: 23
ろんり
問題の条件
Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Example 2:
Input: nums = [1]
Output: 1
Example 3:
Input: nums = [5,4,-1,7,8]
Output: 23問題の条件
私の考えの論理
このような配列がある場合はindex 0から1~4->index 1から2~4まで…このように続けていく方法です.
-どれも新しい配列に入れて比較するO(n^3)よりいいのかな…?
解答(Kadane'sアルゴリズムを使用)
レポートは
に答える var maxSubArray = function(nums) {
1) var sum = nums[0];
var max = sum;
for(let i = 1; i < nums.length ; i++){
2) sum=(sum+nums[i])>nums[i]?(sum+nums[i]):nums[i];
3) max=sum>max?sum:max;
}
return max;
};
1)インデックスの初期値をsumの初期値に設定します.maxは、追加した数値をインデックスの値と比較して、より大きな値を得る.
2)インデックス値を前の連続加算時の最大値と比較し、より大きな値を返します.
Reference
この問題について(Maximum Subarray), 我々は、より多くの情報をここで見つけました
https://velog.io/@sgr2134/Maximum-Subarray
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
var maxSubArray = function(nums) {
1) var sum = nums[0];
var max = sum;
for(let i = 1; i < nums.length ; i++){
2) sum=(sum+nums[i])>nums[i]?(sum+nums[i]):nums[i];
3) max=sum>max?sum:max;
}
return max;
};
Reference
この問題について(Maximum Subarray), 我々は、より多くの情報をここで見つけました https://velog.io/@sgr2134/Maximum-Subarrayテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol