美味しいご飯を食べたので、箸休めに頑張りたいと思います。
ある配列 k1、k2、、、、kn-1、kn
がある時、任意の数 i と j 個前の数 kj-kiの差が最大になるアルゴリズムを求める。
ただし、
0≦n≦200,000
0≦k≦109
j ＜ i
とする。
処理速度も考えるものとする。
１．愚直に書いたやつ
<pre class="lang:default decode:true" title="愚直に書いたやつ">let array = [];
let maxVal;
let minVal;
let sum;
let getNextValue;
for( i=0; i < 100000; i++){
array.push(Math.floor(Math.random() * 200000) + 1);
}
minVal = array[1];
maxVal = array[2];
sum = maxVal - minVal;
getNextValue = false;
for(k=3; k < 100000; k++ ){
if(minVal < array[k]){
if(maxVal < array[k] || getNextValue == true){
getNextValue = false;
maxVal = array[k];
if(sum < (maxVal - minVal)){
sum = (maxVal - minVal);
console.log('checkSum:' + sum);
}
}
} else {
minVal = array[k];
getNextValue = true;
}
}なんか違うらしい。
解説を見ると、というか。
配列の添え字は連番と決まっているのだからもっとシンプルにできそう。
getNextValue の所が要らなくなるな・・・。
減らした。
<pre class="lang:default decode:true " title="減らした">minVal = array[1];
maxVal = array[2];
sum = maxVal - minVal;
for(k=3; k < 100000; k++ ){
if(minVal < array[k]){
if(maxVal < array[k]){
maxVal = array[k];
if(sum < (maxVal - minVal)){
sum = (maxVal - minVal);
console.log('checkSum:' + sum);
}
}
} else {
minVal = array[k];
maxVal = array[k + 1];
}
}配列のライブラリとかを使うともっと減らせそうだけど。
聡明な明日の私がなんとかしてくれると思います。
ネットの皆様の声も募集しております。