# 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 Solution :

### Constraints :

• 1 <= nums.length <= 105

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

## 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.

### Related Banners

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

## 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