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.