最長遞增子序列 子串

Problem statement:

問題陳述：

Given a sequence of numbers you have to find out the length of the longest increasing odd even subsequence and print the length of the subsequence. The sequence will be maintaining like, (odd ) -> ( even ) -> ( odd ) -> ( even ) or (even ) -> ( odd ) -> ( even ) -> ( odd ) .

給定一個數字序列，您必須找出最長的遞增奇數偶數子序列的長度并打印該子序列的長度。 順序將保持為(odd)->(even)->(奇數)->(偶數)或(even)->(奇數)->(偶數)->(奇數) 。

Input:
T Test case
T no. of input array along with their element no. N
E.g.
3
8
2 3 4 8 2 5 6 8
8
2 3 4 8 2 6 5 4
7
6 5 9 2 10 77 5
Constrain:
1≤ T ≤ 20
1≤ N ≤50
1≤ A[i] ≤50
Output:
Print the length of the longest increasing 
odd even subsequence

Example

例

T=3
Input:
8
2 3 4 8 2 5 6 8 
Output:
5 ( 2 3 4 5 8  )
Input:
8
2 3 4 8 2 6 5 4
Output:
4 ( 2 3 4 5 )
Input:
7
6 5 9 2 10 77 5
Output:
4 (6 9 10 77 )

Explanation with example:

舉例說明：

Let N be the number of elements say, X₁, X₂, X₃ ... X_n.

令N為元素數，即X ₁ ，X ₂ ，X ₃ ... X _{n 。}

Let odd(a) = the value at the index a of the odd array and even(a) = the value at the index a of the even array.

令odd(a) =奇數數組的索引a處的值，而even(a) =偶數數組的索引a處的值。

To find the length of the longest increasing odd even subsequence we will follow these steps,

要找到最長的遞增奇數偶數子序列的長度，我們將按照以下步驟操作，

1. We take two new array one is an odd array and another is even an array and initialize both with 1. We start our algorithm with the second column. We check elements that are before the current element, with the current element.

   我們采用兩個新的數組，一個是奇數數組，另一個是偶數數組，并都用1初始化。我們從第二列開始我們的算法。 我們使用當前元素檢查當前元素之前的元素。

2. If the current element is odd and the comparing the element is even then,

   如果當前元素為奇數，而比較元素為偶數，

   odd (index of current element) = even (index of the comparing element) + 1 ;

   奇數(當前元素的索引)=偶數(比較元素的索引)+1；

3. If the current element is even and the comparing element is odd then,

   如果當前元素為偶數，而比較元素為奇數，

   even (index of current element) = odd (index of the comparing element) + 1;

   偶數(當前元素的索引)=奇數(比較元素的索引)+1；

C++ Implementation:

C ++實現：

#include <bits/stdc++.h>
using namespace std;
int length_of_subsequence(int* arr, int n)
{
int a[n];
for (int i = 0; i < n; i++) {
a[i] = 1;
}
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (arr[i] % 2 == 0) {
if (arr[j] % 2 == 1 && arr[j] < arr[i]) {
a[i] = max(a[i], a[j] + 1);
}
}
else {
if (arr[j] % 2 == 0 && arr[j] < arr[i]) {
a[i] = max(a[i], a[j] + 1);
}
}
}
}
int Max = 0;
for (int i = 0; i < n; i++) {
Max = max(Max, a[i]);
}
cout << endl;
return Max;
}
int main()
{
int t;
cout << "TestCase : ";
cin >> t;
while (t--) {
int n;
cout << "Enter number of elements : ";
cin >> n;
int arr[n];
cout << "Enter the elements : ";
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
cout << "Length of the subsequence : " << length_of_subsequence(arr, n) << endl;
}
return 0;
}

Output

輸出量

TestCase : 3
Enter number of elements : 8
Enter the elements : 2 3 4 8 2 5 6 8
Length of the subsequence : 5
Enter number of elements : 8
Enter the elements : 2 3 4 8 2 6 5 4
Length of the subsequence : 4
Enter number of elements : 7
Enter the elements : 6 5 9 2 10 77 5
Length of the subsequence : 4

翻譯自: https://www.includehelp.com/icp/longest-increasing-odd-even-subsequence.aspx

最長遞增子序列 子串