This content originally appeared on DEV Community and was authored by Dev Nirwal
Intuition
We can build the intuition based on the two-point approach.
Approach
We will start with two variables maxSum and maxTillNow.
The first variable stores the max sum we have attained overall in the array.
The second variable stores the value of the maximum sum attained till the current index. Since the array has a negative value, this value will fluctuate, but whenever we get
maxSum < maxTillNow, we update themaxSum.The final case we have to handle will be if the maximum sum till any index reaches zero, i.e.,
maxTillNow < 0, reset themaxTillNow = 0at the end of loop.
Complexity
-
Time complexity: O(N)
-
Space complexity: O(1)
Code
class Solution {
public int maxSubArray(int[] nums) {
int maxSum = Integer.MIN_VALUE;
int maxTillNow = 0;
for(int i =0;i<nums.length;i++){
maxTillNow+=nums[i];
maxSum = Math.max(maxTillNow,maxSum);
if(maxTillNow<0) maxTillNow = 0;
}
return maxSum;
}
}
GitHub repo for more solutions: Git
Leetcode profile: Leetcode: devn007
This content originally appeared on DEV Community and was authored by Dev Nirwal
Dev Nirwal | Sciencx (2025-01-10T18:05:39+00:00) Kadane’s Algorithm: Leetcode 53 Maximum subarray. Retrieved from https://www.scien.cx/2025/01/10/kadanes-algorithm-leetcode-53-maximum-subarray/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.