Maximum Subarray LeetCode Soution

Maximum Subarray LeetCode Solution :

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

The Maximum Subarray Problem can be solved using various algorithms, including the Kadane’s algorithm, which efficiently finds the maximum subarray sum in a single pass through the array. 

Maximum Subarray leetcode

Maximum Subarray LeetCode Solution :

Constraints :

  • 1 <= nums.length <= 105

  • -104 <= nums[i] <= 104

maximum leetcode solution

Approach for Maximum Subarray LeetCode Solution : :

  1. We start by initializing two variables: maxSum and currentSum.
    • maxSum represents the maximum sum encountered so far and is initially set to the minimum possible integer value to ensure that any valid subarray sum will be greater than it.
    • currentSum represents the current sum of the subarray being considered and is initially set to 0.
  2. We iterate through the nums array using a for loop, starting from the first element and going up to the last element.
  3. For each element in the array, we add it to the current sum currentSum. This calculates the sum of the subarray ending at the current element.
  4. Next, we check if the current sum currentSum is greater than the current maximum sum maxSum.
    • If it is, we update maxSum with the new value of currentSum. This means we have found a new maximum subarray sum.
  5. If the current sum currentSum becomes negative, it indicates that including the current element in the subarray would reduce the overall sum. In such cases, we reset currentSum to 0. This effectively discards the current subarray and allows us to start a fresh subarray from the next element.
  6. We repeat steps 3 to 5 for each element in the array.
  7. After iterating through the entire array, the variable maxSum will contain the maximum subarray sum encountered.
  8. Finally, we return the value of maxSum as the result, representing the maximum sum of a contiguous subarray within the given array nums.

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Code for Maximum Subarray LeetCode Solution : :

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription