Leetcode #3 Maximum Subarray

It's been a while. It was quite busy the past week so thus the lack of posts. I solved a few more problems but now I think I would only post questions that I find challenging or worth putting on here because I'm not posting daily. Leetcode May competition is also coming up so I might start with the newer ones. Recently I also started learning django, a framework for python. I only set up the environment for it though, and I haven't started written anything yet, but I'm looking forward to that. Let's get straight into the question

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. Example: Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6. 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.

This question is actually a pretty famous question and there's a really good solution using the kadane's algorithm

The kadane's algorithm requires us to keep track of two variables, one for the maximum subarray sum, which is the answer we want, and another for the current subarray sum, which is self-explanatory. I named it mx and curr respectively.

Now it gets to the important part. We don't like it when the next number makes the substring less than the current substring. max(nums[num], curr + nums[num]) updates curr so if the next number causes the number to become less than 0, we will reset curr to become the current number. This is a bit confusing so here is an example: Say we have an array like this [1, 2, -5, 4. Curr would be 3 in the first iteration because 1 + 2 = 3, the second iteration will make curr -2, which makes the subarray less than 0. Now when we iterate to the third index, the max(4, -2+4) would be 4, which is ideal because we don't want the subarray with a negative value anymore. Now you might think how will we keep track of the largest subarray if it just iterates through the entire thing? This is where the mx variable comes into play. Mx keeps track of the max subarray, which gives us the answer. This is kind of complicated so don't worry if you don't get it, just try writing it yourself or going through the code and you'll get the idea. Or ask a question below and I'll answer it. I'll see you next time

-Rex