> For the complete documentation index, see [llms.txt](https://nuoxu2016.gitbook.io/algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://nuoxu2016.gitbook.io/algorithms/dynamic-programming.md).

# 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 |

```java
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&#x20;

| 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]

```java
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

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

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

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

0 0 0 0 0 0&#x20;

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`, 并且还可以继续往前追溯（如果前面还能连起来的话)

```python
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)
```