Dynamic Programming
- build(arr)
- dp(arr)
- kadane_recursive(arr)[source]
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
It is recursive version of Kadane’s Algorithm. Example of Recursive DP (I prefer recursive DP since it’s much more comfortable to me)
Time complexity: \(O(n)\)
Space complexity: \(O(n)\)
- Return type:
int
- max_subarray_product(arr)[source]
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest product and return its product.
Time complexity: \(O(n)\)
Space complexity: \(O(1)\)
- Return type:
int
- max_subarray_sum(arr)[source]
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Classic Kadane’s Algorithm
Time complexity: \(O(n)\)
Space complexity: \(O(1)\)
- Return type:
int
- max_subarray_sum_circular(arr)[source]
Given a circular integer array nums of length n, return the maximum possible sum of a non-empty subarray of nums. A circular array means the end of the array connects to the beginning of the array.
Time complexity: \(O(n)\)
Space complexity: \(O(1)\)
- Return type:
int
- range_gcd_queries(arr)[source]
- Given an array of n numbers, we need to efficiently answer q queries of the form:
What is the greatest common divisor of elements from index l to r (with 0-based indexing)?
Time complexity: \(O(n^2)\)
Space complexity: \(O(n^2)\)
- Return type:
Tuple[Callable[[List[int]], List[int]], Callable[[List[int], int, int], int]]
- range_min_queries(arr)[source]
- Given an array of n numbers, we need to efficiently answer q queries of the form:
What is the minimum/maximum element from index l to r (with 0-based indexing)?
Time complexity: \(O(n^2)\)
Space complexity: \(O(n^2)\)
- Return type:
Tuple[Callable[[List[int]], List[int]], Callable[[List[int], int, int], int]]