Maximum Sum of Non-Adjacent Subarrays
MediumPractice library · +20 XPdynamic programmingarraysgreedy
Given an array of N integers, find the maximum possible sum of elements such that no two chosen elements are adjacent in the original array. You can choose to not pick any element, in which case the sum is 0.
Input
The first line contains a single integer N. The second line contains N space-separated integers, representing the array elements.
Output
Print a single integer, the maximum sum of non-adjacent elements.
Constraints
1 <= N <= 200000, -10^9 <= a_i <= 10^9
Time limit 1 s (native code; slower languages get more)Memory 256 MB14 hidden tests
Example 1
Input
5 1 2 3 4 5
Output
9
Choose 1, 3, 5 for a sum of 9. Or 2, 4 for a sum of 6. Max is 9.
Example 2
Input
4 2 -1 3 -2
Output
5
Choose 2 and 3 for a sum of 5.
Hints
Similar problems
- Maximum Sum of Non-Adjacent Elements in a Circular ArrayMedium
- Maximum Sum of Consecutive SubsegmentsMedium
- Longest Subarray with Constant DifferenceMedium
- Max Consecutive SumMedium
- Minimum Operations to Make Array SortedMedium
- Maximum Sum of Non-overlapping SubarraysMedium
More topics: Arrays problems, 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 -2