MAXSUM2 - Tổng tiền 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
Nhị vừa học về tổng tiền tố, và thầy giáo của anh cho anh bài toán sau:
Cho dãy số A gồm n số nguyên ~a_1, a_2, ..., a_n~.
- Gọi ~f(i, j) = |a_i| + |a_i+1| + ... + |a_j|~. Tìm giá trị lớn nhất của ~f(i, j)~ với ~1 ≤ i ≤ j ≤ n~.
- Gọi ~g(i, j) = a_i + a_i+1 + ... + a_j~. Tìm giá trị lớn nhất của ~g(i, j)~ với ~1 ≤ i ≤ j ≤ n~.
Sau khi giải xong hai bài toán trên một cách dễ dàng, Nhị nhận thấy hai hàm ~f(i, j)~ và ~g(i, j)~ không có liên quan gì đến nhau, vì vậy anh đề xuất một bài toán hại não hơn cho các thí sinh Free Contest:
Cho dãy số ~A~ gồm ~n~ số nguyên ~a_1, a_2, ..., a_n~. Tìm giá trị lớn nhất của ~f(i, j) + g(i, j)~ với ~1 ≤ i ≤ j ≤ n~.
Input
- Dòng đầu tiên chứa số nguyên dương ~n (1 ≤ n ≤ 5 × 10^5)~.
- Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n (|a_i| ≤ 10^9~.
Output
- Gồm một dòng chứa một số nguyên dương duy nhất là kết quả của bài toán.
Sample
Input #1
5
-3 5 -10 8 -2
Output #1
26
Problem source: Kc97ble - Free Contest 40
Bình luận
C++ (/ˈsiː plʌs plʌs/, prononcé « C plus plus » et parfois abrégé en CPP) est un langage de programmation de haut niveau et polyvalent, créé par l'informaticien danois Bjarne Stroustrup. Initialement publié en 1985 comme extension du langage de programmation C, il a connu depuis de nombreux développements. En 1997, C++ offrait des fonctionnalités orientées objet, génériques et fonctionnelles, ainsi que des fonctionnalités de manipulation de mémoire de bas niveau pour des systèmes comme les micro-ordinateurs ou pour la création de systèmes d'exploitation comme Linux ou Windows. Il est généralement implémenté sous forme de langage compilé, et de nombreux éditeurs proposent des compilateurs C++, notamment la Free Software Foundation, LLVM, Microsoft, Intel, Embarcadero, Oracle et IBM.[14]
C++ a été conçu pour la programmation système, les logiciels embarqués à ressources limitées et les grands systèmes, avec comme points forts la performance, l'efficacité et la flexibilité d'utilisation.[15] Le C++ s'est également révélé utile dans de nombreux autres contextes, ses principaux atouts étant les infrastructures logicielles et les applications à ressources limitées[15], notamment les applications bureautiques, les jeux vidéo, les serveurs (par exemple, le commerce électronique, la recherche web ou les bases de données) et les applications critiques en termes de performances (par exemple, les commutateurs téléphoniques ou les sondes spatiales).[16]
Le C++ est normalisé par l'Organisation internationale de normalisation (ISO). La dernière version de la norme a été ratifiée et publiée par l'ISO en octobre 2024 sous le nom d'ISO/IEC 14882:2024 (connue officieusement sous le nom de C++23).[17] Le langage de programmation C++ a été initialement normalisé en 1998 sous le nom d'ISO/IEC 14882:1998, puis amendé par les normes C++03, C++11, C++14, C++17 et C++20. La norme C++23 actuelle les remplace par de nouvelles fonctionnalités et une bibliothèque standard enrichie. Avant sa standardisation initiale en 1998, le C++ était développé par Stroustrup chez Bell Labs depuis 1979 comme une extension du langage C ; il souhaitait un langage efficace et flexible, similaire à C, offrant également des fonctionnalités avancées pour l'organisation des programmes.[18] Depuis 2012, le C++ est publié sur trois ans[19], C++26 étant la prochaine norme prévue.[20]
Malgré son adoption généralisée, le langage C++ a été critiqué par certains programmeurs de renom, notamment Linus Torvalds, Richard Stallman, Joshua Bloch, Ken Thompson et Donald Knuth. Cela est dû en grande partie à sa gestion manuelle de la mémoire, qui le rend vulnérable aux bogues de dépassement de tampon, représentant un risque de sécurité.
Lỗi đánh máy không phải a[i] + a[i] + 1 + a[i] + 2 + ... + a[j] đâu mà phải là a[i] + a[i + 1] + a[i + 2] + ... + a[j] (i <= j)