資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究最長遞增子序列
最長遞增子序列是一個子序列，其中某個專案項大於其前一個專案項。在此，我們將嘗試找到一組整數中的最長遞增子序列長度。
輸入輸出
Input:
A set of integers. {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}
Output:
The length of longest increasing subsequence. Here it is 6.
The subsequence is 0, 2, 6, 9, 13, 15.演算法
longestSubSeq(subarray, n)
輸入 − 子陣列和子陣列的大小。
輸出 − 最長遞增子序列長度。
Begin define array length of size n initially set 0 to all entries of length for i := 1 to n-1, do for j := 0 to i-1, do if subarray[j] < subarray[i] and length[j] > length[i], then length[i] := length[j] done increase length[i] by 1 done lis := 0 for i := 0 to n-1, do lis := maximum of lis and length[i] done return lis End
範例
#include <iostream>
using namespace std;
int longestSubSeq(int subArr[], int n) {
int length[n] = { 0 }; //set all length to 0
length[0] = 1; //subsequence ending with subArr[0] is 1
for (int i = 1; i < n; i++) { //ignore first character, second to all
for (int j = 0; j < i; j++) { //subsequence ends with subArr[j]
if (subArr[j] < subArr[i] && length[j] > length[i])
length[i] = length[j];
}
length[i]++; //add arr[i]
}
int lis = 0;
for (int i = 0; i<n; i++) // find longest increasing subsequence
lis = max(lis, length[i]);
return lis;
}
int main() {
int arr[] = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
int n = 16
cout << "Length of Longest Increasing Subsequence is: " << longestSubSeq(arr, n);
return 0;
}輸出
Length of Longest Increasing Subsequence is: 6
最近更新於：2020 年 6 月 16 日
超過 2000 次瀏覽
廣告