資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會科學
時尚研究
法律研究最長的峰形子序列
一個序列被稱作是山形的，當它先遞增後遞減時。在這個問題中，給定一個全是正整數的陣列。我們必須找到一個遞增後遞減的子序列。
為了解決這個問題，我們將定義兩個子序列，它們分別是：最長遞增子序列和最長遞減子序列。LIS 陣列將持有以 array[i] 結尾的遞增子序列長度。LDS 陣列將儲存從 array[i] 開始的遞減子序列長度。使用這兩個陣列，我們就能獲得最長山形子序列的長度。
輸入與輸出
Input:
A sequence of numbers. {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}
Output:
The longest bitonic subsequence length. Here it is 7.演算法
longBitonicSub(array, size)
輸入：陣列，陣列長度。
輸出：最長山形子序列的最大長度。
Begin define incSubSeq of size same as the array size initially fill all entries to 1 for incSubSeq for i := 1 to size -1, do for j := 0 to i-1, do if array[i] > array[j] and incSubSeq[i] < incSubSum[j] + 1, then incSubSum[i] := incSubSum[j] + 1 done done define decSubSeq of size same as the array size. initially fill all entries to 1 for incSubSeq for i := size - 2 down to 0, do for j := size - 1 down to i+1, do if array[i] > array[j] and decSubSeq[i] < decSubSum[j] + 1, then decSubSeq [i] := decSubSeq [j] + 1 done done max := incSubSeq[0] + decSubSeq[0] – 1 for i := 1 to size, do if incSubSeq[i] + decSubSeq[i] – 1 > max, then max := incSubSeq[i] + decSubSeq[i] – 1 done return max End
示例
#include<iostream>
using namespace std;
int longBitonicSub( int arr[], int size ) {
int *increasingSubSeq = new int[size]; //create increasing sub sequence array
for (int i = 0; i < size; i++)
increasingSubSeq[i] = 1; //set all values to 1
for (int i = 1; i < size; i++) //compute values from left ot right
for (int j = 0; j < i; j++)
if (arr[i] > arr[j] && increasingSubSeq[i] < increasingSubSeq[j] + 1)
increasingSubSeq[i] = increasingSubSeq[j] + 1;
int *decreasingSubSeq = new int [size]; //create decreasing sub sequence array
for (int i = 0; i < size; i++)
decreasingSubSeq[i] = 1; //set all values to 1
for (int i = size-2; i >= 0; i--) //compute values from left ot right
for (int j = size-1; j > i; j--)
if (arr[i] > arr[j] && decreasingSubSeq[i] < decreasingSubSeq[j] + 1)
decreasingSubSeq[i] = decreasingSubSeq[j] + 1;
int max = increasingSubSeq[0] + decreasingSubSeq[0] - 1;
for (int i = 1; i < size; i++) //find max length
if (increasingSubSeq[i] + decreasingSubSeq[i] - 1 > max)
max = increasingSubSeq[i] + decreasingSubSeq[i] - 1;
return max;
}
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 bitonic subsequence is " << longBitonicSub(arr, n);
}輸出
Length of longest bitonic subsequence is 7
更新於： 16-06-2020
286 次瀏覽
廣告