Link Sub: http://www.spoj.com/PTIT/problems/P171SUME/
Người Gửi: Vô Danh
- Problem:
Cho một dãy a gồm N phần tử, tìm hai dãy con có tổng lớn nhất: 1, Dãy con gồm các phần tử liên tiếp
2, Dãy con gồm các phần tử không cần thiết phải liên tiếp
Dãy con phải có số phần tử >=1.
Hãy in ra tổng lớn nhất của 2 loại dãy con.
Input
Dòng đầu là số N (N<=10^5)
Dòng tiếp theo gồm các số ai (-10^5<=ai<=10^5)
Output
1 dòng duy nhất ghi tổng lớn nhất của 2 lại dãy con, 2 số cách nhau 1 dấu cách.
Số đầu tiên là tổng của dãy con liên tiếp, số còn lại là kết quả của trường hợp còn lại.
Example:
1 dòng duy nhất ghi tổng lớn nhất của 2 lại dãy con, 2 số cách nhau 1 dấu cách.
Số đầu tiên là tổng của dãy con liên tiếp, số còn lại là kết quả của trường hợp còn lại.
Input
5
1 2 3 4 5
Output:
15 15
Input
8
1 2 -4 -5 -6 1 2 3
Output:
6 9
- Solution:
Input
8
1 2 -4 -5 -6 1 2 3
Output:
6 9
Các trường hợp tất cả đều âm, tất cả đều dương thì dễ rồi: - Tất cả âm: KQ sẽ là hai số âm lớn nhất. - Tất cả dương: KQ sẽ là hai số là tổng của tất cả các số. Trường hợp cả âm, cả dương: - Nó sẽ hơi hướng QHĐ nhưng khá nhẹ nhàng: + KQ1: Với mỗi phần tử thì (Ai) xét xem khi cộng thêm vào (S_tmp) có tạo ra số dương hay không? Nếu không thì reset nó về 0 (vì nếu có cả dương và âm thì dãy dài nhất mà tổng lớn nhất luôn dương). Nếu tạo ra số dương thì so sánh số đó với giá trị trước đó (S) và lấy cái tổng lớn hơn. + KQ2: tổng tất cả số dương. VD: 5 -1 8 -> 12 13 (p/s: Admin: Biến S_tmp giống như là biến xét tất cả các trường hợp liên tiếp mà tổng của chúng dương vậy thôi!)
1 nhận xét:
nhận xéthay
Reply