Đếm số lượng các mảng con không tăng trong C ++

Cho một mảng arr [] chứa các số nguyên dương. Mục đích là tìm số lượng các mảng con có độ dài ít nhất là 1 không tăng. Nếu arr [] ={1,3,2}, thì các mảng con sẽ là {1}, {2}, {3}, {3,2}. Đếm là 4.

Ví dụ

Đầu vào

arr[] = {5,4,5}

Đầu ra

Count of number of non-increasing subarrays are: 7

Giải thích

The subarrays will be −
{5}, {4}, {5}, {5,4}

Đầu vào

arr[] = {10,9,8,7}

Đầu ra

Count of number of non−increasing subarrays are − 10

Giải thích

The subarrays will be −
{10}, {9}, {8}, {7}, {10,9}, {9,8}, {8,7}, {10,9,8}, {9,8,7}, {10,9,8,7}

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau -

Trong cách tiếp cận này, chúng ta sẽ sử dụng thực tế là nếu các phần tử giữa các chỉ mục i và j trong arr [] không không tăng thì các phần tử giữa các chỉ mục i đến j + 1, i đến j + 2… .i đến j + n-1 không bao giờ có thể không tăng, vì vậy hãy tiếp tục tăng độ dài của mảng con này cho đến khi các phần tử không tăng. Nếu tìm thấy bất kỳ phần tử nào nhỏ hơn arr [j]

• Lấy một mảng số nguyên arr [].

• Các mảng con của hàm (int arr [], int size) nhận mảng và kích thước của nó và trả về số lượng các mảng con không tăng.

• Lấy số lượng ban đầu là 0 và độ dài của mảng con nhỏ nhất là temp =1.

• Traverse arr [] sử dụng vòng lặp for, nếu arr [i + 1] <=arr [i] thì nhiệt độ tăng vì mảng con không tăng.

• Nếu không, hãy thêm (temp + 1) * temp) / 2 để đếm số lượng các mảng con của tầng con có độ dài tạm thời không tăng.

• Đặt temp =1 cho mảng con mới.

• Vào cuối tất cả các vòng lặp, nếu độ dài temp> 1 một lần nữa, hãy thêm (temp + 1) * temp) / 2 để đếm cho mảng con cuối cùng.

• Kết quả là số lượt trả lại.

Ví dụ

#include <bits/stdc++.h>
using namespace std;
int subarrays(int arr[], int size){
   int count = 0;
   int temp = 1;
   for(int i = 0; i < size − 1; ++i){
      if (arr[i + 1] <= arr[i]){
         temp++;
      } else {
         count += (((temp + 1) * temp) / 2);
         temp = 1;
      }
   }
   if(temp > 1){
      count += (((temp + 1) * temp) / 2);
   }
   return count;
}
int main(){
   int arr[] = {2, 6, 1, 8, 3};
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"Count of number of non−increasing subarrays are: "<<subarrays(arr, size);
   return 0;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -

Count the number of non-increasing subarrays are: 7