LeetCodeベストTOP面接問題53.最大サブシーケンス和
6646 ワード
タイトルの説明
整数配列numsを指定し、最大和を持つ連続サブ配列(サブ配列には少なくとも1つの要素が含まれている)を見つけ、その最大和を返します.
問題を解く構想.
考え方1
動的計画–時間複雑度O(N)、空間複雑度O(1)(1)下付き1から配列の遍歴を開始し、現在の要素itemの前の要素preが0より大きい場合、itemはitem+preに更新され、そうでない場合は遍歴を継続する. (2)は、Math.max(max,item)関数を使用して現在の最大値とitem値のサイズを比較して、巡回中に最終的な最大和を決定する.考え方2 貪欲アルゴリズム–時間複雑度O(N),空間複雑度O(1)現在の要素の前の要素シーケンスの和が0未満の場合、この「和」 は破棄される.定義tempは、「現在の要素」と「現在の要素の前の要素シーケンスの和」を比較するために使用されます.
分治法–時間複雑度O(N),空間複雑度O(logn)という考え方は公式問題解を見て初めて理解できるものであり,最適アルゴリズムではなく,最適アルゴリズムは依然として動的計画であるが,理解が徹底していないため,ここでは不正確な解釈をしない.詳細はLeetcode公式問題解でお勉強ください.
コード(Java)
構想1コード
考え方2コード
整数配列numsを指定し、最大和を持つ連続サブ配列(サブ配列には少なくとも1つの要素が含まれている)を見つけ、その最大和を返します.
example:
input : -2,1,-3,4,-1,2,1,-5,4
output : 6
note : [4,-1,2,1] ， 6
問題を解く構想.
考え方1
動的計画–時間複雑度O(N)、空間複雑度O(1)
分治法–時間複雑度O(N),空間複雑度O(logn)という考え方は公式問題解を見て初めて理解できるものであり,最適アルゴリズムではなく,最適アルゴリズムは依然として動的計画であるが,理解が徹底していないため,ここでは不正確な解釈をしない.詳細はLeetcode公式問題解でお勉強ください.
コード(Java)
構想1コード
public class Solution2 {
public int maxSubArray(int[] nums){
int max = nums[0];
for (int i = 1; i < nums.length; i++){
if (nums[i-1] > 0){
nums[i] += nums[i-1]; // item[i] item[i-1]>0,
}
max = Math.max(nums[i], max); //
}
return max;
}
}
考え方2コード
public class Solution {
public int maxSubArray(int[] nums){
int temp = nums[0];
int max = nums[0];
for (int i = 1; i < nums.length; i++){
temp = Math.max(nums[i], temp + nums[i]); // “ ” “ ”
// temp = Math.max(0, temp);
max = Math.max(temp, max); //
}
return max;
}
}