cho em xin hướng giải quyết bài này với ạ, em mới chỉ hướng đc bước đầu là trừ tất cả các phần tử của mảng cho k rồi tìm dãy con lớn nhất sao cho tổng lớn hơn bằng 0 thôi ạ
Dãy con liên tiếp
cái này nói chuyện huề vốn
trungbinhcong = tong/n > k thì hiển nhiên tong - n*k > 0 rồi
theo như suy luận bình thường, giải bằng tay của bạn, thì bạn sẽ làm gì? có phải là băt từng cặp đầu - cuối, rồi kiểm tra đoạn từ phần tử đầu đến phần tử cuối đó có trung bình > k rồi ghi nhận không?
2 Likes
em sẽ sắp xếp tăng dần rồi lần lượt cho từng phần tử ở đầu cộng đến cuối khi nào lớn hơn bằng 0 thì đó là dãy con lớn nhất ạ
Không “huề vốn” đâu. Chuyển qua tổng dãy con >= 0 rồi thì tính mảng prefix_sum, bài toán trở thành tìm j - i lớn nhất sao cho prefix_sum[j] >= prefix_sum[i]. Method 4 là O(N).
2 Likes
cách này hay quá em cảm ơn ạ
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?