Maximum Sum of Adjacent Elements
EasyPractice library · +10 XPgreedydynamic programming
Given a list of N integers, find the maximum possible sum you can obtain by picking elements from the list such that no two picked elements are adjacent. You can pick any number of elements, including zero.
Input
The first line contains an integer N. The second line contains N space-separated integers.
Output
Print a single integer representing the maximum sum.
Constraints
1 <= N <= 1000. Integers are between -1000 and 1000.
Time limit 1 s (native code; slower languages get more)Memory 256 MB15 hidden tests
Example 1
Input
5 1 2 3 4 5
Output
9
Pick 1, 3, 5 for sum 9.
Example 2
Input
4 2 -1 3 -4
Output
5
Pick 2, 3 for sum 5.
Hints
Similar problems
- Longest Alternating SubsequenceMedium
- Maximum Sum of Non-Overlapping SubsegmentsMedium
- Maximum Sum of Consecutive SubsegmentsMedium
- Maximum Sum of Non-Adjacent Elements in a Circular ArrayMedium
- Maximum Sum of Non-Overlapping Positive SubarraysMedium
- Maximum Sum of Non-Adjacent SubarraysMedium
More topics: Greedy problems, Dynamic Programming problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
5 1 2 3 4 5
Example 2 input
4 2 -1 3 -4