Dãy con

[cuong276]

[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

Có ai biết thuật toán tìm dãy con có tổng lớn nhất trong dãy với độ phức tạp là O(n) không nhỉ?
Không dùng thuật toán kadane với QHĐ nha. Duyệt trâu bò thôi

 

[lamdetien36]

Cái này có khác Kadane không nhỉ :-/

int main() {
    int A[100], N, i, T, T_min, V;

    cin >> N;
    for (i = 0; i < N; ++i)
        cin >> A[i];

    T = V = A[0];
    T_min = min(0, T);
    for (i = 1; i < N; ++i) {
        T += A[i];
        if (T - T_min > V)
            V = T - T_min;
        if (T < T_min)
            T_min = T;
    }

    cout << V;
    return 0;
}