MAXSUM - Dãy con có tổng lớn nhất
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, Python, Ruby, Rust, Scratch, Swift
Cho mảng ~A~ gồm ~N~ phần tử. Tìm dãy con gồm các phần tử liên tiếp ~S~ của dãy ~A~ sao cho tổng tất cả các phần tử của ~S~ là lớn nhất và in ra tổng đó.
Input
- Dòng đầu, chứa số nguyên dương ~N~ ~(1 ≤ N ≤ 1000)~;
- Dòng tiếp theo gồm ~N~ số nguyên ~A_i~ ~(−10^9 ≤ A_i ≤ 10^9)~.
Output
- Gồm một số nguyên duy nhất là kết quả của bài toán.
Sample
Input #1
3
1 -3 3
Output #1
3
Problem source: Kc97ble - Free Contest
Bình luận
Ý tưởng cho ae nào quả bí : tư tưởng là preFixSum trước hết anh em tạo mảng S[n+1] phần tử ,S[0]=0, tính tổng các phần tử đoạn [a[0]->a[i]] bằng công thức S[i]=S[i-1]+a[i-1];//tự hiểu nhé -Ở đây nó không giống bài đoạn con có k phần tử cố định , mà phần tử đoạn k có thể thay đổi ,để sao cho tổng sẽ phải lớn nhất từ a[l]->a[r],Vậy ta cứ cố định r trước nhé (r chạy từ 1 ->n) , ta cần tìm *max(S[r]-S[l])*.. (l chạy từ 0 đến r-1), như bạn ở trên bảo duyệt 2 vòng for đẻ tìm cũng được nhưng nó không hay . -S[r] cố định rồi thì ta cần tìm max(-S[l]) đó cũng chính là cần tìm min (S[l]) (tự giải thích nhé ) =>vậy công việc sẽ là tìm min S[l] tại từng vị trí thì ta xét mảng preFMin có n+1 phần tử như sau : preFmin[0]=0;//không chọn thằng nào , từ i=1 đến i<=n thì preFmin[i]=min(preFmin[i-1],prefSum[i]), nghĩa là ta so sánh và chọn thằng nhỏ hơn giữa 2 thằng này Cuối cùng ta sẽ tìm max giữa preF[i]-preFmin[i-1],i chạy từ 1 đến n là AC.. FAN MU MÃI ĐỈNH...
dung hai vong for long nhau cung duoc ma :33
TLE chắc chắn luôn á
Hi. Mình comment cái này với mục đích cho bạn nào chưa biết hoặc đã làm được bài trên nhưng muốn tìm hiểu thêm cách làm mới thôi nha. Thuật toán Kadane giúp giải quyết bài toán này nhanh gọn với vỏn vẹn vài dòng code thôi ý
Các bạn có thể tham khảo lí thuyết để giải bài này ở đây https://wiki.vnoi.info/algo/data-structures/prefix-sum-and-difference-array.md
Bài này input mỗi số trong mảng A nằm trên một dòng.
Cảm ơn bạn,mìn code đúng mà nộp bài toàn báo sai cho đến khi đọc được comment của bạn
Ai giải thích giúp mình với, mình nộp kadane vẫn ac trong khi trường hợp mà cả dãy A là số dương thì lại sai??
là do test chưa quét hết th hay sao v?