Dynamic Programming
1. Maximum Subarray

Maximum Subarray (opens in a new tab) Medium

Problem

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: nums = [-2,1,-3,4,-1,2,1,-5,4]

Output: 6

Explanation: [4,-1,2,1] has the largest sum = 6.

Summary

To solve this problem, we can use dynamic programming to keep track of the maximum sum subarray ending at each position. We can iterate through the array and calculate the maximum subarray ending at the current position by choosing between the current element and the sum of the current element with the maximum subarray ending at the previous position.

Solution

In TypeScript

function maxSubArray(nums: number[]): number {
    let maxSum = nums[0];
    let currentSum = nums[0];
 
    for (let i = 1; i < nums.length; i++) {
        currentSum = Math.max(currentSum + nums[i], nums[i]);
        maxSum = Math.max(maxSum, currentSum);
    }
 
    return maxSum;
}

In Python

def maxSubArray(self, nums: List[int]) -> int:
		maxSum = nums[0]
		currentSum = nums[0]
 
		for i in range(1, len(nums)):
				currentSum = max(currentSum + nums[i], nums[i])
				maxSum = max(maxSum, currentSum)
 
		return maxSum

Step-by-step explanation

  1. First, we initialize two variables maxSum and currentSum with the value of the first element of the input array nums.
let maxSum = nums[0];
let currentSum = nums[0];
  1. We start iterating through the array from the second element (index 1) to the last element.
for (let i = 1; i < nums.length; i++) {
		// ...
}
  1. For each element, we calculate the maximum subarray sum ending at the current position. We have two choices: include the current element in the subarray by adding it to currentSum or start a new subarray starting from the current element. We choose the option with the larger sum.
currentSum = Math.max(currentSum + nums[i], nums[i]);
  1. We update the global maximum subarray sum (maxSum) by comparing it with the current subarray sum (currentSum). If the current subarray sum is larger, we update maxSum.
maxSum = Math.max(maxSum, currentSum);
  1. After the loop finishes, we return the global maximum subarray sum maxSum.
return maxSum;

In summary, the algorithm iterates through the array and keeps track of the maximum subarray sum ending at each position. At each step, it decides whether to include the current element in the subarray or start a new subarray. The algorithm has a linear time complexity and constant space complexity.

Complexity Analysis

Time Complexity

The time complexity of this solution is O(n), where n is the length of the input array. We iterate through the array once, updating the maximum subarray sum at each position.

Space Complexity

The space complexity of this solution is O(1) since we only use constant extra space to keep track of the maximum sum subarray and the current subarray sum.

9. Basic Calculator II2. Coin Change