Diwali Offer!Flat 20% OFF
Enroll Now
PrakalpanaLive online tech training

4. Maximum Subarray

MediumDay 1 of 60Arrays & Hashing

Given an integer array nums, find the contiguous subarray (with at least one element) that has the largest sum, and return that sum.

Example 1
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
The subarray [4,-1,2,1] adds up to 6.
Example 2
Input: nums = [5,4,-1,7,8]
Output: 23
Taking the whole array is best.
Constraints
  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4
Hints
Frequently asked at: Amazon, Microsoft, Google, Adobe, Flipkart, TCS, Infosys
Ctrl + Enter runs the examples

Not sure what to learn next?

A 1-on-1 session with an industry mentor and a roadmap built for you. How it works

  1. 1Discuss your goals
  2. 2Get a personal plan
  3. 3Start learning
Book for β‚Ή200/ 30 min