This is an easy Leetcode problem 53. See below image for description:
ALGORITHM
1.Have a global variable currentSum;
2.Have a global variable max that will also be the return value;
3.Loop through the array, check if the current element (nums[i]) is greater than the current sum and current element put together (i.e currentSum + nums[i]);
4.if it is greater, reassign the currentSum variable to be the current element, nums[i];
5.if it is not, reassign the currentSum variable to be the summation of both the existing current sum and the current array element (currentSum = currentSum + nums[i])
6.finally, check if the currentSum is greater than the current maximum. if it is, reassign the current max to be equal to currentSum.
7.Then return max.
CODE
public static int maxSubArray(int[] nums) {
int currentSum = nums[0];
int max = nums[0];
for (int i = 1; i < nums.length; i++) {
if (nums[i] > (currentSum + nums[i]))
currentSum = nums[i];
else
currentSum = currentSum + nums[i];
if (currentSum > max) {
max = currentSum;
}
}
return max;
}
IMPROVEMENT
Math.max checks the maximum/bigger value between two numbers. So we can replace those if statements with Math.max(). Cleaner code is shown below:
IMPROVED CODE
public static int maxSubArray(int[] nums) {
int currentSum = nums[0];
int max = nums[0];
for (int i = 1; i < nums.length; i++) {
//cleaner and simple
currentSum = Math.max(nums[i], currentSum + nums[i]);
max = Math.max(currentSum, max);
}
return max;
}
LESSONS
1.Don’t always be in the box of a particular algorithm you thought would work, just the way i thought Sliding window would work.
2.Using library functions where and when needed.
Thank you for reading. Please leave a comment.
Top comments (0)