Maximum Sum of Non-Adjacent Elements
HardPractice library · +30 XPbasicsdynamic programmingarrays
Given an array of N integers, find the maximum sum of a subsequence such that no two elements in the subsequence are adjacent in the original array. The integers can be positive, negative, or 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 possible sum.
Constraints
1 <= N <= 200000 -10^9 <= A[i] <= 10^9
Time limit 1 s (native code; slower languages get more)Memory 256 MB16 hidden tests
Example 1
Input
5 1 2 3 4 5
Output
9
Include 1, 3, 5 for a sum of 9. Or include 2, 4 for a sum of 6. Max is 9.
Example 2
Input
3 -1 -2 -3
Output
0
It's better to pick no elements for a sum of 0 than any negative elements.
Hints
Similar problems
- Count Consecutive OccurrencesEasy
- Count Numbers Divisible by KEasy
- Maximum Sum Subarray with Length ConstraintHard
- Longest Non-Decreasing SubsequenceHard
- Print Array in ReverseEasy
- Maximum Sum of Non-Adjacent SubarraysMedium
More topics: Arrays problems, Dynamic Programming problems, Beginner Coding Problems 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
3 -1 -2 -3