Solution to Leetcode’s Maximum Subarray

Leetcode 53: problem description
  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.
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;
}
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;
}
  1. Don’t always been 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.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store