Maximum Subarray Sum Circular
Python
Hard
3 views
Problem Description
Read n integers (can be negative). Compute maximum subarray sum in circular array and output it.
Input Format
First line n. Second line n integers.
Output Format
One integer maxSum.
Official Solution
import sys
p=sys.stdin.read().strip().split()
if not p: sys.exit(0)
n=int(p[0])
a=list(map(int,p[1:1+n]))
max_end=a[0]
max_so=a[0]
min_end=a[0]
min_so=a[0]
total=a[0]
for x in a[1:]:
total+=x
max_end = x if x>max_end+x else max_end+x
if max_end>max_so:
max_so=max_end
min_end = x if x<min_end+x else min_end+x
if min_end<min_so:
min_so=min_end
if max_so<0:
sys.stdout.write(str(max_so))
else:
best=max_so
wrap=total - min_so
if wrap>best:
best=wrap
sys.stdout.write(str(best))
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!