Understand what the interviewer is asking for by using test cases and questions about the problem.
- Established a set (2-3) of test cases to verify their own solution later.
- Established a set (1-2) of edge cases to verify their solution handles complexities.
- Have fully understood the problem and have no clarifying questions.
- Have you verified any Time/Space Constraints for this problem?
HAPPY CASE
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Input: nums = [5,4,-1,7,8]
Output: 23
EDGE CASE
Input: nums = [1]
Output: 1
Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.
Whenever you see a question that asks for the maximum or minimum of something, consider Dynamic Programming as a possibility. If you want to forego the brute force approach, a more optimal solution for obtaining the maximum sub-array is Kadane’s algorithm. Two significant variables used is: current maximum to keep track of whether or not the value at the current index would increase the maximum sum and maximum so far to keep track of the overall maximum that is propagated along the array.
Plan the solution with appropriate visualizations and pseudocode.
1. Initialize 2 integer variables. Set both of them equal to the first value in the array.
currentSubarray will keep the running count of the current subarray we are focusing on.
maxSubarray will be our final return value. Continuously update it whenever we find a bigger subarray.
2. Iterate through the array, starting with the 2nd element (as we used the first element to initialize our variables). For each number, add it to the currentSubarray we are building. If currentSubarray becomes negative, we know it isn't worth keeping, so throw it away. Remember to update maxSubarray every time we find a new maximum.
3. Return maxSubarray.
⚠️ Common Mistakes
The algorithm will find the continuous subarray in the 1D integer array which has the largest sum possible. The first approach for everyone after understanding the problem statement will be applying the brute-force approach and solving the problem. But by doing so, the time complexity of the solution will be O(N^2) which isn't ideal. We need to solve the problem by traversing over the whole array using two variables to track the sum so far and maximum total.
Implement the code to solve the algorithm.
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
# initialize our variables using the first element.
current_subarray = max_subarray = nums[0]
# start with the 2nd element since we already used the first one.
for num in nums[1:]:
# if current_subarray is negative, throw it away. Otherwise, keep adding to it.
current_subarray = max(num, current_subarray + num)
max_subarray = max(max_subarray, current_subarray)
return max_subarray
class Solution {
public int maxSubArray(int[] nums) {
// initialize our variables using the first element.
int currentSubarray = nums[0];
int maxSubarray = nums[0];
// start with the 2nd element since we already used the first one.
for (int i = 1; i < nums.length; i++) {
int num = nums[i];
// if current_subarray is negative, throw it away. Otherwise, keep adding to it.
currentSubarray = Math.max(num, currentSubarray + num);
maxSubarray = Math.max(maxSubarray, currentSubarray);
}
return maxSubarray;
}
}
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Evaluate the performance of your algorithm and state any strong/weak or future potential work.