Maximum Sum of Non-Adjacent Elements in a Circular Array
MediumPractice library · +20 XPdynamic programminggreedyarrays
Given a circular array of N integers, find the maximum sum you can obtain by selecting non-adjacent elements. You cannot select adjacent elements. Since the array is circular, the first and last elements are considered adjacent.
Input
The first line contains an integer N (2 <= N <= 200000). The second line contains N space-separated integers a_1, a_2, ..., a_N (-10^9 <= a_i <= 10^9).
Output
Print a single integer, the maximum possible sum.
Constraints
2 <= N <= 200000, -10^9 <= a_i <= 10^9
Time limit 2 s (native code; slower languages get more)Memory 256 MB15 hidden tests
Example 1
Input
5 1 2 3 4 5
Output
8
We can pick 1, 3, 5 for sum 9. Or pick 2, 4 for sum 6. Max is 9.
Example 2
Input
4 10 -3 5 -8
Output
15
We can pick 10, 5 for sum 15. Or pick -3, -8 for sum -11. Max is 15.
Hints
Similar problems
- Maximum Sum of Non-Adjacent SubarraysMedium
- Maximum Sum of Consecutive SubsegmentsMedium
- Max Consecutive SumMedium
- Minimum Operations to Make Array SortedMedium
- Maximum Sum of Non-Overlapping SubsegmentsMedium
- Longest Alternating SubsequenceMedium
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 10 -3 5 -8