let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Overview

NKMAXSEQ - Dãy con dài nhất

solution.md

Ta tính mảng tổng \(S[i]\) là tổng từ \(A[1]\) đến \(A[i]\), \(S[0] = 0\). Sau đó sắp xếp lại mảng \(S\) tăng dần (có lưu lại chỉ số ban đầu của phần tử).

Lần lượt duyệt các phần tử trong mảng đã sắp lại. Ở \(S[i]\), vì đề yêu cầu tổng của dãy con phải không nhỏ hơn \(p\) nên ta cần tìm \(j\) lớn nhất thỏa \(S[i]-S[j]\geq p\). Khi đó dãy con dài nhất tại \(S[i]\) là \(I[i]-min\{I[k] \mid 0 \leq k \leq j\}\), \(I\) là mảng chỉ số ban đầu của các phần tử trong dãy \(S\).

Để tìm \(j\), có thể sử dụng tìm kiếm nhị phân, cho độ phức tạp của lời giải là \(O(N \log N)\). Tuy nhiên, do ta duyệt \(i\) tăng dần nên \(j\) cũng sẽ tăng dần theo \(i\) Từ đó có cách làm \(O(N)\) như bên dưới, tại mỗi bước ta tăng \(j\) trong khi điều kiện \(S[i]-S[j]\geq p\) còn thỏa.

main.cpp
Open in Github • Download 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int,int> pii;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    int n, p; cin >> n >> p;
    vector<pii> s(n+1);
    s[0] = {0, 0};
    for (int i=1; i<=n; i++) {
        int a; cin >> a;
        s[i] = {s[i-1].first + a,i};
    }

    sort(s.begin(), s.end());
    int res = 0;
    int min_index = n;
    for (int i=0, j=-1; i<=n; i++) {
        while (j<n && s[i].first-s[j+1].first >= p) {
            min_index = min(min_index, s[++j].second);
        }
        if (j>=0) {
            res = max(res, s[i].second - min_index);
        }
    }

    if (res == 0) res = -1;
    cout << res;
    return 0;
}
Comments