資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究C++程式：查詢最長位數等差子序列的長度
假設我們有一組數字。我們需要找到最長位數等差子序列的長度。我們知道，如果一個序列先嚴格遞增，然後嚴格遞減，則稱其為位數等差序列。嚴格遞增序列也是位數等差序列。嚴格遞減序列也是位數等差序列。
因此，如果輸入類似於nums = [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]，序列大小為16，則輸出為7。
為了解決這個問題，我們將遵循以下步驟：
建立一個與給定陣列大小相同的新陣列increasingSubSeq，並將其填充為1
初始化 i := 1，當 i < size 時，更新（i增加1），執行：
初始化 j := 0，當 j < i 時，更新（j增加1），執行：
如果 arr[i] > arr[j] 且 increasingSubSeq[i] < increasingSubSeq[j] + 1，則：
increasingSubSeq[i] := increasingSubSeq[j] + 1
建立一個與給定陣列大小相同的新陣列decreasingSubSeq，並將其填充為1
初始化 i := size - 2，當 i >= 0 時，更新（i減少1），執行：
初始化 j := size - 1，當 j > i 時，更新（j減少1），執行：
如果 arr[i] > arr[j] 且 decreasingSubSeq[i] < decreasingSubSeq[j] + 1，則：
decreasingSubSeq[i] := decreasingSubSeq[j] + 1
max := increasingSubSeq[0] + decreasingSubSeq[0] - 1
初始化 i := 1，當 i < size 時，更新（i增加1），執行：
如果 increasingSubSeq[i] + decreasingSubSeq[i] - 1 > max，則
max := increasingSubSeq[i] + decreasingSubSeq[i] - 1
返回 max
讓我們看看下面的實現，以便更好地理解：
示例
#include<iostream>
using namespace std;
int longBitonicSub( int arr[], int size ) {
int *increasingSubSeq = new int[size];
for (int i = 0; i < size; i++)
increasingSubSeq[i] = 1;
for (int i = 1; i < size; i++)
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];
for (int i = 0; i < size; i++)
decreasingSubSeq[i] = 1;
for (int i = size-2; i >= 0; i--)
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++)
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 << longBitonicSub(arr, n);
}輸入
[0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15], 16
輸出
7
149 次瀏覽
