LeetCode配列編(四):ベスト観光グループ
タイトル
正の整数配列Aが与えられ、A[i]はi番目の観光スポットのスコアを表し、2つのスポットiとjとの間の距離はj−iである.
一対の観光地(i観光スポットペアで取れる最高点を返します.
例:
ヒント:
第1の方法-暴力の解
二重サイクル(技術的な難点はない).
第2の方法(株の売買最大収益の問題に鑑みる)
O(n)の時間的複雑度による問題解決
組み合わせ得点A[i]+A[j]+i-jで位置を入れ替える
(A[i]+iの最大値)と(A[j]-j)の和になる
現在の要素A[j]-jが一定値(各要素自体について)であるため、この要素の観光最高得点は、現在の要素の前の要素集合におけるA[i]+iの最大値を求めることに変換される
コードは次のとおりです.
正の整数配列Aが与えられ、A[i]はi番目の観光スポットのスコアを表し、2つのスポットiとjとの間の距離はj−iである.
一対の観光地(i
例:
：[8,1,5,2,6]
：11
：i = 0, j = 2, A[i] + A[j] + i - j = 8 + 5 + 0 - 2 = 11
ヒント:
2 <= A.length <= 50000
1 <= A[i] <= 1000
第1の方法-暴力の解
二重サイクル(技術的な難点はない).
class Solution {
public int maxScoreSightseeingPair(int[] A) {
int maxScore = 0;
// （ ）
for(int i = 0; i < A.length; i++){
int maxFirstScore = A[i] + i;
for (int j = i+1; j < A.length; j++){
if (maxScore < maxFirstScore + A[j] - j){
maxScore = maxFirstScore + A[j] - j;
}
}
}
return maxScore;
}
}
第2の方法(株の売買最大収益の問題に鑑みる)
O(n)の時間的複雑度による問題解決
組み合わせ得点A[i]+A[j]+i-jで位置を入れ替える
(A[i]+iの最大値)と(A[j]-j)の和になる
現在の要素A[j]-jが一定値(各要素自体について)であるため、この要素の観光最高得点は、現在の要素の前の要素集合におけるA[i]+iの最大値を求めることに変換される
コードは次のとおりです.
class Solution {
public int maxScoreSightseeingPair(int[] A) {
int maxFirstScore = A[0];
int maxScore = 0;
for (int i = 1; i < A.length; i++){
//
if((maxFirstScore + A[i] - i) > maxScore){
maxScore = maxFirstScore + A[i] - i;
}
//
if (maxFirstScore < (A[i] + i)){
maxFirstScore = A[i] + i;
}
}
return maxScore;
}
}