BL
U

42. Maximum Subarray Sum (Kadane's Algorithm)

Med.

Problem Description

Given an array of NN integers, find the maximum sum of a non-empty contiguous subarray.

Input Format

  • •Line 1: An integer NN (1≤N≤1051 \le N \le 10^5).
  • •Line 2: NN space-separated integers A1,…,ANA_1, \dots, A_N.

Output Format

Print the maximum contiguous subarray sum.

Example 1:
Input:
9
-2 1 -3 4 -1 2 1 -5 4
Output:
6
Explanation: Subarray [4, -1, 2, 1] has the largest sum = 6.
Example 2:
Input:
1
-5
Output:
-5
Explanation: Single negative element has sum -5.
Example 3:
Input:
5
5 4 -1 7 8
Output:
23
Explanation: Entire array sum is 23.
Constraints:
  • Standard integer bounds: 32-bit signed integer or input range [1, 10^5].
  • Time complexity target: O(N) or O(N log N) where applicable.
  • Auxiliary space target: O(1) or minimal auxiliary memory.
Follow up:Can this algorithm be adapted to an online streaming setting where the entire input cannot be held in memory simultaneously?
1,180 Online