資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律C++ 中最長算術序列
假設我們有一個整數陣列 A，我們需要返回 A 中最長算術子序列的長度。眾所周知，A 的子序列是 A[i_1]、A[i_2]、...、A[i_k] 的列表，其中 0 <= i_1 < i_2 < ... < i_k <= A.length - 1，並且序列 B 當 B[i+1] - B[i] 全部具有相同的值時（對於 0 <= i < B.length - 1）為算術序列。因此，如果輸入類似於 [9,4,7,2,10]，則輸出將為 3。因為最長的子序列是 [4,7,10]。
為了解決這個問題，我們將遵循以下步驟 -
建立一個對映 dp，n := A 的大小，設定 ret := 2
對於 i 的範圍從 0 到 n – 1
對於 j 的範圍從 0 到 i – 1
diff := A[j] – A[i]
dp[i, diff] := 1 + dp[j, diff]
ret := 1 + dp[i, diff] 和 ret 的最大值
返回 ret
讓我們看看以下實現以獲得更好的理解 -
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int longestArithSeqLength(vector<int>& A) {
unordered_map <int, unordered_map <int, int> > dp;
int n = A.size();
int ret = 2;
for(int i = 0; i < n; i++){
for(int j = 0; j < i; j++){
int diff = A[j] - A[i];
dp[i][diff] = 1 + dp[j][diff];
ret = max(1 + dp[i][diff], ret);
}
}
return ret;
}
};
main(){
vector<int> v1 = {9,4,7,2,10};
Solution ob;
cout << (ob.longestArithSeqLength(v1));
}輸入
[9,4,7,2,10]
輸出
3
更新於: 2020-04-30
281 次瀏覽
廣告