Computer >> Máy Tính >  >> Lập trình >> C ++

Chương trình tìm độ dài của dãy con bitonic dài nhất trong C ++

Giả sử chúng ta có một danh sách các số. Chúng ta phải tìm độ dài của dãy con bitonic dài nhất. Khi chúng ta thắt nút một chuỗi được cho là bitonic nếu nó tăng nghiêm ngặt và sau đó giảm xuống nghiêm ngặt. Trình tự tăng dần đáng kể là bitonic. Hoặc một chuỗi giảm dần cũng là bitonic.

Vì vậy, nếu đầu vào giống như nums =[0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15], kích thước của chuỗi 16, thì đầu ra sẽ là 7.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

  • TăngSubSeq:=mảng mới với kích thước mảng đã cho và điền bằng 1

  • để khởi tạo i:=1, khi i

    • để khởi tạo j:=0, khi j

      • nếu arr [i]> arr [j] và tăngSubSeq [i]

        • TăngSubSeq [i]:=TăngSubSeq [j] + 1

      • * ReduceSubSeq:=mảng mới với kích thước mảng đã cho và điền bằng 1

    • để khởi tạo i:=size - 2, khi i> =0, cập nhật (giảm i đi 1), thực hiện -

      • để khởi tạo j:=size - 1, khi j> i, cập nhật (giảm j đi 1), thực hiện -

        • nếu arr [i]> arr [j] và ReduceSubSeq [i]

          • giảm dầnSubSeq [i]:=ReduceSubSeq [j] + 1

        • tối đa:=tăngSubSeq [0] + giảm dầnSubSeq [0] - 1

      • để khởi tạo i:=1, khi i

        • nếu tăngSubSeq [i] + giảmSubSeq [i] - 1> tối đa, thì:

          • tối đa:=tăngSubSeq [i] + giảm dầnSubSeq [i] - 1

        • trả về tối đa

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ 

#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);
}

Đầu vào 

[0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15], 16

Đầu ra 

7