## DP

### 最大对角矩阵

1. $f(i-1,j-1)$
2. $i,j$ 左边 0 的数量
3. $i,j$ 上边 0 的数量

https://youtu.be/tW0zwL2ar7s?t=4254

## 刷题

### 最长和谐子数组

3 4 9 1 2 1 2 1 2 9 5 3  ok len maxlen
[3] 4 9 1 2 1 2 1 2 9 5 3 v	1	1
[3 4] 9 1 2 1 2 1 2 9 5 3 v	2	2
[3 4 9] 1 2 1 2 1 2 9 5 3 x	3	3
3 [4 9] 1 2 1 2 1 2 9 5 3 x	2	3
3 4 [9] 1 2 1 2 1 2 9 5 3 x	1	3
3 4 9[] 1 2 1 2 1 2 9 5 3 x	0	3
3 4 9 [1] 2 1 2 1 2 9 5 3 v	1	3
3 4 9 [1 2] 1 2 1 2 9 5 3 v	2	3
3 4 9 [1 2 1] 2 1 2 9 5 3 v	3	3
3 4 9 [1 2 1 2] 1 2 9 5 3 v	4	4
3 4 9 [1 2 1 2 1] 2 9 5 3 v	5	5
3 4 9 [1 2 1 2 1 2] 9 5 3 v	6	6
3 4 9 [1 2 1 2 1 2 9] 5 3 x	7	6
3 4 9 1 [2 1 2 1 2 9] 5 3 v	6	6
3 4 9 1 2 [1 2 1 2 9] 5 3 v	5	6
3 4 9 1 2 1 [2 1 2 9] 5 3 v	4	6
3 4 9 1 2 1 2 [1 2 9] 5 3 v	3	6
3 4 9 1 2 1 2 1 [2 9] 5 3 v	2	6
3 4 9 1 2 1 2 1 2 [9] 5 3 v	1	6
3 4 9 1 2 1 2 1 2 9[] 5 3 v	0	6
3 4 9 1 2 1 2 1 2 9 [5] 3 v	1	6
3 4 9 1 2 1 2 1 2 9 5[] 3 v	0	6
3 4 9 1 2 1 2 1 2 9 5 [3] v	1	6
ret = 7

3 4 9 1 2 1 2 1 2 9 5 3  ok len maxlen
[3] 4 9 1 2 1 2 1 2 9 5 3 v	1	1
[3 4] 9 1 2 1 2 1 2 9 5 3 v	2	2
[3 4 9] 1 2 1 2 1 2 9 5 3 x	3	3
3 4 [9] 1 2 1 2 1 2 9 5 3 v	1	3 // 一旦出界，就重置 l 到 r-1
3 4 [9 1] 2 1 2 1 2 9 5 3 x	0	3
3 4 9 [1] 2 1 2 1 2 9 5 3 v	1	3
3 4 9 [1 2] 1 2 1 2 9 5 3 v	2	3
3 4 9 [1 2 1] 2 1 2 9 5 3 v	3	3
3 4 9 [1 2 1 2] 1 2 9 5 3 v	4	4
3 4 9 [1 2 1 2 1] 2 9 5 3 v	5	5
3 4 9 [1 2 1 2 1 2] 9 5 3 v	6	6
3 4 9 [1 2 1 2 1 2 9] 5 3 x	6	6
3 4 9 1 2 1 2 1 2 [9] 5 3 v	1	6 // 一旦出界，就重置 l 到 r-1
3 4 9 1 2 1 2 1 2 [9 5] 3 x	1	6
3 4 9 1 2 1 2 1 2 9 [5] 3 v	0	6
3 4 9 1 2 1 2 1 2 9 5 [3] v	1	6
ret = 7

#include <debug.h>

class Solution {
public:
int findLHS(vector<int> &v) {
int n = v.size();
bool ok = true;
int maxlen = 0, l = 0, r = 0;
int i_min = 0, i_max = 0;
while (l <= r && r < n) {
ok = v[i_max] - v[i_min] == 1;
if (ok) {
maxlen = max(maxlen, r - l + 1);
printf("l = %d\n", l);
printf("r = %d\n", r);
print_vec_part(v, l, r + 1);
r++;
if (r < n) {
i_min = v[r] < v[i_min] ? r : i_min;
i_max = v[r] > v[i_max] ? r : i_max;
}
} else {
l = r;
i_min = l;
i_max = l;
}
}
return maxlen;
}
};
int main(int argc, char const *argv[]) {
Solution s;
std::vector<int> v = {1, 3, 2, 2, 5, 2, 3, 7};
cout << s.findLHS(v) << endl;
return 0;
}

### 594. 最长和谐子序列

class Solution {
public:
int find(std::vector<int> &v, int from, int offset) {
int maxv = v[from];
int minv = v[from];
int len = 0;
for (int i = from; i < v.size(); i++) {
if (v[from] == v[i] || v[from] == v[i] + offset) {
len++;
maxv = max(maxv, v[i]);
minv = min(minv, v[i]);
}
}
if (maxv - minv != 1) {
return 0;
}
return len;
}
int findLHS(vector<int> &v) {
int maxlen = 0;
for (int i = 0; i < v.size(); i++) {
maxlen = max (maxlen, find (v, i, 1)); // 统计 x, x+1 子序列
maxlen = max (maxlen, find (v, i, -1)); // 统计 x, x-1 子序列
}
return maxlen;
}
};

{1, 3, 2, 2, 5, 2, 3, 7};
|
此时我们想知道后面有多少个等于 3 或 4 的，多少个等于 3 或 2 的

{1, 3, 2, 2, 5, 2, 3, 7};
-->
{1, 2, 2, 2, 3, 3, 5, 7}
[           ]
class Solution {
public:
int findLHS(vector<int> &v) {
sort(v.begin(), v.end());
int l = 0, r = 1, maxlen = 0, n = v.size();
while (l < r && r < n) {
while (l < r && v[r] - v[l] > 1) {
l++;
}
if (v[r] - v[l] == 1) {
maxlen = max(maxlen, r - l + 1);
}
r++;
}
return maxlen;
}
};