DevHireLab
TutorialsBootcamp
ProblemsCode SimulatorAI InterviewSoonContact
DevHireLab
TutorialsBootcamp
ProblemsCode SimulatorAI InterviewSoonContact
Back to Arena
easy
Array

Max Subarray Sum (Kadane's)

**Problem Statement:** Given an integer array `nums`, find the subarray with the largest sum, and return its sum. **Hint / Expected Approach:** Local max vs global max tracking **Edge Cases to Consider:** - (1) All negative numbers - (2) Single element - (3) All zeros

Examples

Example 1
Input: [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Example 2
Input: [1]
Output: 1
Example 3
Input: [5,4,-1,7,8]
Output: 23

Constraints

  • ▪1 <= nums.length <= 10^4
  • ▪-10^9 <= nums[i] <= 10^9
  • ▪Time complexity should be O(n) or O(n log n)

Watch Out For Edge Cases

  • ▪All negative numbers
  • ▪Single element
  • ▪All zeros
Frequently Asked At
MicrosoftMetaAmazonAdobeFlipkartInfosys