Kadane Algorithm — Maximum Subarray Sum

Practice this coding question on Coding Gurukul.

Problem statement

Given an array of signed integers, find the maximum sum of a nonempty contiguous subarray using Kadane’s algorithm. A subarray must use consecutive elements. You cannot skip elements inside it or choose an empty subarray. Print only the maximum sum. If all values are negative, print the largest single value. Use O(n) time, O(1) extra space and signed 64-bit sums. Worked example The consecutive values [4, -1, 2, 1] have sum 6. No other nonempty subarray has a greater sum.

Input format

First line: n. Second line: n signed integers.

Output format

Print the maximum nonempty subarray sum.

Constraints

1 <= n <= 200000; -10^9 <= a[i] <= 10^9.

Sample input

8
-2 -3 4 -1 2 1 -5 4

Sample output

6

Sign in to run or submit a solution in C++, Java or Python.