NST0 - Đoạn con có tổng không âm
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift
Cho số nguyên dương N và dãy N số nguyên ai .Một đoạn con của dãy là dãy các phần tử liên tiếp nhau.
Hãy xác định độ dài đoạn con dài nhất của A có tổng không âm.
Input
-Dòng 1: Chứa số nguyên dương N(~ 1 \le N \le 10^5 ~)
-Dòng 2: Chứa N số nguyên ~ a_i ~(~ a_i \le 10^4 ~)
Output
Kết quả tìm được. Nếu không có ghi -1
Sample
Input #1
6
-7 0 -2 6 -6 -4
Output #1
3
Hint
Ở test 1 từ ~ a_2 ~ đến ~ a_4 ~ có tổng là 4 (~ 0 \le 4 ~) nên 3 phần tử liên tiếp là đáp án của đề bài !!
Problem source: THCS Lập Thạch
Bình luận
Tạo mảng cộng dồn preF[n+1] , preF[0]=0, preF[i]=preF[i-1]+a[i-1]; =>Tổn đoạn [i,j] sẽ phải là preF[j+1]-preF[i]=(a[0]+a[1]+..+a[j])-(a[0]+..+a[i-1])=a[i]+a[i-1]+...+a[j]