# Problem

Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.

Note:
If n is the length of array, assume the following constraints are satisfied:

• 1 ≤ n ≤ 1000
• 1 ≤ m ≤ min(50, n)

Examples:

Input:
nums = [7,2,5,10,8]
m = 2

Output:
18

Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8],
where the largest sum among the two subarrays is only 18.


# Solution: DP

Time complexity: O(n^2*m)

Space complexity: O(n*m)

C++ / Recursion + Memorization

C++ / DP

# Solution: Binary Search

Time complexity: O(log(sum(nums))*n)

Space complexity: O(1)

# Problem

https://leetcode.com/problems/longest-mountain-in-array/description/

Let’s call any (contiguous) subarray B (of A) a mountain if the following properties hold:

• B.length >= 3
• There exists some 0 < i < B.length - 1 such that B[0] < B[1] < ... B[i-1] < B[i] > B[i+1] > ... > B[B.length - 1]

(Note that B could be any subarray of A, including the entire array A.)

Given an array A of integers, return the length of the longest mountain.

Return 0 if there is no mountain.

Example 1:

Input: [2,1,4,7,3,2,5]
Output: 5
Explanation: The largest mountain is [1,4,7,3,2] which has length 5.


Example 2:

Input: [2,2,2]
Output: 0
Explanation: There is no mountain.


Note:

1. 0 <= A.length <= 10000
2. 0 <= A[i] <= 10000

# Solution: DP

Three passes

Time complexity: O(n)

Space complexity: O(n)

C++

One pass

Time complexity: O(n)

Space complexity: O(1)

# Problem

There is an m by n grid with a ball. Given the start coordinate (i,j) of the ball, you can move the ball to adjacent cell or cross the grid boundary in four directions (up, down, left, right). However, you can at most move N times. Find out the number of paths to move the ball out of grid boundary. The answer may be very large, return it after mod 109 + 7.

Example 1:

Input:m = 2, n = 2, N = 2, i = 0, j = 0
Output: 6
Explanation:



Example 2:

Input:m = 1, n = 3, N = 3, i = 0, j = 1
Output: 12
Explanation:



Note:

1. Once you move the ball out of boundary, you cannot move it back.
2. The length and height of the grid is in range [1,50].
3. N is in range [0,50].

# Solution

Time complexity: O(m*n + N * m * n)

Space complexity: O(N*m*n) -> O(m*n)

C++

Recursion with memorization

no loops

# Problem

https://leetcode.com/problems/longest-palindromic-subsequence/description/

Given a string s, find the longest palindromic subsequence’s length in s. You may assume that the maximum length of s is 1000.

Example 1:
Input:

"bbbab"


Output:

4


One possible longest palindromic subsequence is “bbbb”.

Example 2:
Input:

"cbbd"


Output:

2


One possible longest palindromic subsequence is “bb”.

# Solution: DP

Time complexity: O(n^2)

Space complexity: O(n^2)

C++

Time complexity: O(n^2)

Space complexity: O(n)

C++

Python3

C#

# Problem

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

Input: nums =
[
[9,9,4],
[6,6,8],
[2,1,1]
]
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9].

Example 2:

Input: nums =
[
[3,4,5],
[3,2,6],
[2,2,1]
]
Output: 4
Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

# Solution1: DFS + Memorization

Time complexity: O(mn)

Space complexity: O(mn)

C++

# Solution2: DP

DP

Time complexity: O(mn*log(mn))

Space complexity: O(mn)

Mission News Theme by Compete Themes.