アルゴリズム-leetcode-毎日1題-最大のサブ配列を求めます
1907 ワード
分析:この问题は1本の経典の问题で、しかし多くの人は理解できなくて、私はここで総括を行って、みんなは私の考えによって见て、きっと理解することができます.は蛮力法を用いる.最外ループはi番目の数であり、第2ループはiから配列尾jまで、最内ループはiからjまでのサブ配列の和を計算する. この方式はiからjの間の値を繰り返し計算し,繰り返し計算をどのように減らすかに重点を置いており,最内のkサイクルではSum[I,j]=Sum[I,j-1]+arr[j]により繰り返し計算を回避できる. は、上記の2つのスキームの重畳順序と、第2の解の理解に注意する.動的最適化は依然として重複を減らす演算である.上記のアルゴリズムでは,固定iでのjの繰返し計算のみを除去したが,iが変化するとsumの部分値は依然として繰返しである.どうやって問題を分解しますか?A[1,j]の最も大きなサブ配列が知られている場合、A[1,j+1]の最も大きなサブ配列は、最後の要素arr[n−1]と最も大きなサブ配列との関係を解くことに等しい.1最も大きなサブ配列はarr[n−1]を含み、すなわちarr[n−1]で終わる.2 arr[n−1]は、最も大きなサブ配列を単独で構成する.③最大サブ配列はarr[n−1]を含まない.3種類は、All[i-1]=max{arr[i-1],End[i-1],All[i-2]}と書くことができ、3つの選択肢は対応①②③③に分けられる.End[i]はi番目の値を含む最大のサブ配列であり、All[i]は現在の最大のサブ配列である. では,End[n−1]とAll[n−1]のみが用いられ,2つの変数を定義するだけでよい.
public static int maxSubArray(int arr[]) {
int n = arr.length;
int ThisSum = 0, MaxSum = 0;
for(int i=0; i MaxSum) { MaxSum = ThisSum; }
}
}
return MaxSum;
}
public static int maxSubArray(int arr[]) {
int size = arr.length;
int maxSum = Integer.MAX_VALUE;
for(int i=0; i maxSum) { maxSum = sum; }//
}
}
return maxSum;
}
public static int maxSubArray(int arr[]) {
int n = arr.length;
int End[] = new int[n];//End[i]
int All[] = new int[n];//All[i]
End[0] = All[0] = arr[0];// arr[0]
for(int i=1; i public static int maxSubArray4(int arr[]) {
int n = arr.length;
int nAll = arr[0];
int nEnd = arr[0];
for(int i=1; i