Skip to content

problem9.md

Latest commit

 

History

History
16 lines (12 loc) · 433 Bytes

problem9.md

File metadata and controls

16 lines (12 loc) · 433 Bytes

Problem 9: The Maximum Subarray (Kadane's Algorithm)

Problem Statement

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Input Format

  • An array of integers nums.

Constraints

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4

Example

Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6
Explanation: The subarray [4, -1, 2, 1] has the largest sum 6.