Maximum Subarray

LeetCode Question 53 Medium

Krishna Shrivastava

December 27, 2025

31 views

LeetCode Array Medium

LeetCode Problem 53

Link of the Problem to try -: Link

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

Example 1:

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.

Example 2:

Input: nums = [1]

Output: 1

Explanation: The subarray [1] has the largest sum 1.

Example 3:

Input: nums = [5,4,-1,7,8]

Output: 23

Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

Constraints:

1 <= nums.length <= 105

-104 <= nums[i] <= 104

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

My Approach -:

I successfully addressed this problem by implementing nested loops to generate the required subarrays. My approach effectively handles the subarray creation logic as specified. Please find the implementation code below.

int ans=0;

for(int i=0;i<nums.length;i++){

int sum =0;

for(int j =i;j<nums.length;j++){

sum += nums[j];

ans = Math.max(sum,ans);

}

return ans;

Although this solution passed local tests, it encountered a 'Time Limit Exceeded' (TLE) error on LeetCode due to the constraints of the problem. While the nested loop approach is logically sound, further optimization is required to improve its time complexity for larger test cases.

Optimized Algorithm (Kadane's Algorithm)

This algorithm is highly efficient, solving the problem in a single pass with a time complexity of O(n), not O(1) constant time, as the algorithm must iterate through all n elements of the input array.

The core principle is based on the idea that any negative prefix sum acts as a 'debt' that subsequent positive numbers must overcome. The strategy is to always pursue the maximum sum. If the running sum becomes negative at any point, it is reset to zero, effectively 'discarding' the previous negative sequence, and the search for a new maximum sum begins with the next element.

Here is a video for more better understanding

My Understanding Steps to solve this Question

To solve this problem efficiently in (O(n)) time, I implemented the following steps:

Initialization: Define two integer variables: currentSum (initialized to 0) and maxSum (initialized to Integer.MIN_VALUE). currentSum tracks the running total, while maxSum stores the overall maximum subarray sum found so far.
Iteration: Traverse the array using a single for loop.
Update Running Sum: At each element, add its value to currentSum.
Update Maximum: Compare currentSum with maxSum. If currentSum is greater, update maxSum with this new value.
Reset Negative Sums: If currentSum drops below zero, reset it to 0. This effectively "discards" a negative prefix that would otherwise reduce the sum of subsequent subarrays.
Return Result: After the loop completes, return maxSum as the final result.

Here is the Code:

int sum = 0;

int max = Integer.MIN_VALUE;

for(int i=0;i <nums.length;i++){

sum +=nums[i];

max =Math.max(sum,max);

if(sum < 0){

sum =0;

}

return max;

(Note this same solution can also write in another way as well)

Here is another way to write this same solution:

int sum = 0;

int max = Integer.MIN_VALUE;

for(int i=0;i <nums.length;i++){

// sum +=nums[i];

sum = Math.max(sum+nums[i],nums[i]); // Here we are ensuring that sum will alwaays be grestest in all time so that it will not be negative or smaller ass previously we directly putting value in it.

max =Math.max(sum,max);

// if(sum < 0){ We don't need this as we already ensure that sum will never be negative and always a positive number

// sum =0;

// }

}

return max;