Max Chunks để tạo thành phân loại II trong C ++

Giả sử chúng ta có một dãy số nguyên, chúng ta phải chia mảng thành một số phân vùng và sắp xếp riêng từng phân vùng. Bây giờ sau khi nối chúng, chúng ta sẽ nhận được một mảng đã được sắp xếp. Chúng ta phải tìm số lượng phân vùng tối đa mà chúng ta có thể tạo ra?

Vì vậy, nếu đầu vào là [3,2,4,5,5], thì đầu ra sẽ là 4, vì chúng ta có thể tạo các phân vùng như [3,2], [4], [5], [5].

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

• cnt:=1

• n:=kích thước của arr

• Xác định một mảng maxOfLeft có kích thước n

• Xác định một mảng minOfRight có kích thước n

• maxOfLeft [0]:=arr [0]

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

  • maxOfLeft [i]:=maxOfLeft [i - 1] và arr [i]

• minOfRight [n - 1] =arr [n - 1]

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

  • minOfRight [i]:=tối thiểu là minOfRight [i + 1] và arr [i]

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

  • nếu minOfRight [i + 1]> =maxOfLeft [i], thì -

    • (tăng cnt lên 1)

• trả lại cnt

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

Ví dụ

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int maxChunksToSorted(vector<int>& arr) {
      int cnt = 1;
      int n = arr.size();
      vector<int> maxOfLeft(n);
      vector<int> minOfRight(n);
      maxOfLeft[0] = arr[0];
      for (int i = 1; i < n; i++)
         maxOfLeft[i] = max(maxOfLeft[i - 1], arr[i]);
         minOfRight[n - 1] = arr[n - 1];
      for (int i = n - 2; i >= 0; i--)
         minOfRight[i] = min(minOfRight[i + 1], arr[i]);
      for (int i = 0; i < n - 1; i++) {
         if (minOfRight[i + 1] >= maxOfLeft[i])
         cnt++;
      }
      return cnt;
   }
};
main(){
   Solution ob;
   vector<int> v = {3,2,4,5,5};
   cout << (ob.maxChunksToSorted(v));
}

Đầu vào

{3,2,4,5,5}

Đầu ra

4