Tách mảng trong C++

Cho mảng nums. Kiểm tra có thể chia thành hai phần không rỗng sao cho mọi số bên trái nhỏ hơn chặt mọi số bên phải hay không.

Ví dụ: [6,4,3,8,10] → true (trái [6,4,3], phải [8,10]).

Giải thuật: Tính mảng leftMax[i] = max từ đầu đến i, rightMin[i] = min từ i đến cuối. Nếu tồn tại i mà leftMax[i] < rightMin[i+1] thì trả về true.

Ví dụ

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool solve(vector<int>& nums) {
        int n = nums.size();
        vector<int> right(n), left(n);
        left[0] = nums[0];
        right[n-1] = nums[n-1];
        for (int i = 1; i < n; i++)
            left[i] = max(left[i-1], nums[i]);
        for (int i = n-2; i >= 0; i--)
            right[i] = min(right[i+1], nums[i]);
        for (int i = 0; i < n-1; i++)
            if (left[i] < right[i+1]) return true;
        return false;
    }
};

int main() {
    Solution ob;
    vector<int> v = {6,4,3,8,10};
    cout << (ob.solve(v));
}

Đầu vào

{6,4,3,8,10}

Đầu ra

1