アルゴリズム 配列の差の最大値を求める

美味しいご飯を食べたので、箸休めに頑張りたいと思います。

ある配列 k1、k2、、、、kn-1、kn

がある時、任意の数iとj個前の数kj-kiの差が最大になるアルゴリズムを求める。

ただし、

0≦n≦200,000

0≦k≦109

j<i

とする。

処理速度も考えるものとする。

 

1.愚直に書いたやつ

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の所が要らなくなるな・・・。

減らした。

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];
	}
}

 

配列のライブラリとかを使うともっと減らせそうだけど。

聡明な明日の私がなんとかしてくれると思います。

ネットの皆様の声も募集しております。

 

シェアする

  • このエントリーをはてなブックマークに追加

フォローする