Dynamic Programming

Longest Ascending Subsequence

Examples Input: A = {5, 2, 6, 3, 4, 7, 5} Output: 4 Because [2, 3, 4, 5] is the longest ascending subsequence.

5

2

6

3

4

7

5

1

1

2

2

3

4

4

public class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int maxans = 1;
        for (int i = 1; i < dp.length; i++) {
            int maxval = 0;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    maxval = Math.max(maxval, dp[j]);
                }
            }
            dp[i] = maxval + 1;
            maxans = Math.max(maxans, dp[i]);
        }
        return maxans;
    }
}

Longest Ascending Subarray

M[i] represent within the range from the beginning to the i-th element, the max length of the ascending subarray

5

1

2

0

1

7

0

1

1

2

1

2

3

1

M [ i ] = M [ i -1] + 1 if num [ i ] > num [ i - 1 ] else M [ i ] = M [ i - 1]

public int subarray(int[] array){
    if(array.length == 0){
        return 0;
    }
    int globalMax = 0;
    int[] dp = new int[array.length];
    dp[0] = 1;
    for(int i = 1; i < array.length; i++){
        if(array[i] > array[i-1]){
            dp[i] = dp[i-1] + 1;
        } else{
            dp[i] = dp[i-1];
        }
        globalMax = max(globalMax , dp[i])l
    }
    return globalMax;   
}

Longest Valid Partentheses

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。

输入: "(()" 输出: 2 解释: 最长有效括号子串为 "()" 示例 2:

输入: ")()())" 输出: 4 解释: 最长有效括号子串为 "()()"

0 0 0 0 0 0

0 0 2 2 4 4

  1. 用一个dp数组来存放以每个index为结尾的最长有效括号子串长度，例如：dp[3] = 2代表以index为3结尾的最长有效括号子串长度为2

  2. 很明显dp[i]和dp[i-1]之间是有关系的

  • 当s[i] == ‘(’时，dp[i]显然为0, 由于我们初始化dp的时候就全部设为0了，所以这种情况压根不用写

  • 当s[i] == ')'时， 如果在dp[i-1]的所表示的最长有效括号子串之前还有一个'('与s[i]对应，那么dp[i] = dp[i-1] + 2, 并且还可以继续往前追溯（如果前面还能连起来的话)

def func(s):
    if len(s) == 0:
        return 0
    dp = [0] * len(s)
    for i in range(1, len(s)):
        if s[i] == ')':
            left = i - 1 - dp[i - 1]
        if left >= 0 and s[left] == '(':
            dp[i] = dp[i - 1] + 2
            if left > 0:
                dp[i] = dp[i] + dp[left-1]
    return max(dp)

PreviousTreesNextArray

Last updated