subarray の最小スライスに関するコードの質問に対する解決策を見つけようとしています。Kadaneのアルゴリズムの修正版を使用して解決策を考案しました。私は現在、90/100 を取得しており、O(n) のほぼすべてのテストに合格することができました。ただし、「medium_range、増加、減少 (レグス = ~100)、および小さな機能、期待される 5 の 3」を渡すことができないようで、その理由がわかりません。これはおそらく解決策の繰り返しですが、私は少し異なる解決方法を使用しています。
私の論理は次のとおりです。
a) 配列 MinA がある場合、MinA[k] は k から始まり、最小長が 2 の部分配列の最小平均スライスを表します。
b) 次に、MinA をループして配列の最小値を見つけると、これが配列全体の最小平均スライスになります (そして、インデックス位置を返します)
c) この MinA を作成するには、配列の最後から 2 番目の要素から開始し、MinA[A.length -2] は A の最後の 2 つの要素の平均です。
d) カウンターを 1 ポジション左に移動します。MinA[カウンター] は、A[カウンター] と A[カウンター + 1] の平均、または要素カウンターと MinA[カウンター + 1] 内の要素の平均のいずれかでなければなりません。
e) d が真でない場合、これは、MinA[カウンター + 1] が、カウンター + 1 からカウンター + 2 から N までの何らかの要素までの最小平均スライスではないことを意味します。
私は何かが足りないのだろうか？
/*
* Using modified version of Kadane's algorithm
* The key logic is that for an array A of length N,
* if M[k + 1] is the minimum slice of a subarray from k + 1 to any element
* between k+2 to n, then M[k] is either the average of A[k] and A[k + 1], or
* the average of the elements k and the elements in M[k + 1]
*/
function solution(A) {
// you can use console.log for debugging purposes, i.e.
// console.log('this is debug message');
// write your code in JavaScript (ECMA-262, 5th edition)
var minSliceArray = [],
counter = A.length - 2,
currMinSliceLength = 0,
min = Number.POSITIVE_INFINITY,
minIndex = -1;
minSliceArray[counter] = (A[counter] + A[counter + 1]) / 2;
currMinSliceLength = 2;
counter--;
while (counter >= 0) {
var a = (A[counter] + A[counter + 1]) / 2,
b = (A[counter] + minSliceArray[counter + 1] * currMinSliceLength) / (currMinSliceLength + 1) ;
if (a < b) {
minSliceArray[counter] = a;
currMinSliceLength = 2;
} else {
minSliceArray[counter] = b;
currMinSliceLength++;
}
counter--;
}
//loops through the minSliceArray and find the minimum slice
for (var i = 0; i < minSliceArray.length; i++) {
if (minSliceArray[i] < min) {
min = minSliceArray[i];
minIndex = i;
}
}
return minIndex;
}