问题1：
给一个数组a，求 a[i] + a[j] - (j - i) 的最大值。
input:
5 # 数组长度
11 6 5 12 18 # 数组元素
output:
29 # 12 + 18 - (5 - 4)
input:
5 # 数组长度
6 5 4 4 8 # 数组元素
output:
11 # 4 + 8 - (5 - 4)
解题思路：
1、直接暴力 O(n^2), 只能通过 30% 的 case，pass。
2、时间复杂度为 O(n) 的做法：
做法：因为 ans = a[i] + a[j] - (j - i) = a[i] + a[j] + i - j = (a[i] + i) + (a[j] - j)，在遍历一遍数组时，每次更新 ans 和 a[i] + i 的最大值，遍历结束后 ans 就是最终的结果。
注意：之所以这样划分，是因为 a[i] + i 的最大值可以在遍历的过程中更新。
C++实现：
#include <iostream>
#include <cstdio>
using namespace std;
int main() {
int n, num;
scanf("%d", &n);
scanf("%d", &num); // 第一个数
int ans = 0;
int mymax = num + 1; // a[i]+i 的初始值
for(int i = 2; i <= n; i++) {
scanf("%d", &num);
ans = max(ans, num-i+mymax); // 更新 ans
mymax = max(mymax, num+i); // 更新 a[i]+i
}
cout << ans; // 输出结果
return 0;
}
问题2：
给一个 M 行 N 列的 0, 1 数组，求由 1 连通的区块个数 （一个 1 的上下左右或者四条对角线也有 1，则代表相连通）。
input:
3 3 # 数组行，列
0 1 0
1 0 0
1 0 1 # 数组中的元素
output:
2 # 两个区块，右下角一个 1 单独形成一个区块，剩下的 3 个 1形成一个区块。
解题思路：
很经典的回溯法（DFS）求解问题。
1、遍历二维数组，如果数组中的元素为 1，先将区块数 ans 加 1，然后利用回溯法（DFS）求解。
2、在 DFS 中，先把 1 的状态改为 0，然后向它的 8 个方向搜索为 1 的元素，继续调用 DFS 遍历。
3、一个区块找完后，标记为 1 的这些位置会变成 0。返回 1 继续搜索下一个区块。
注意： 数组下标不要越界。
实现技巧：如下，可以用一个 8 行 2 列的数组记录搜索的 8 个方向的偏移位置，然后 for 循环遍历，可以防止写 8 个 if 条件。
| 向左上，左，左下搜索 | 向上，下搜索 | 向右上，右，右下搜索 |
|---|---|---|
| (-1, -1) | (-1, 0) | (-1, 1) |
| (0, -1) | 1（周围8个方向） | (0, 1) |
| (1, -1) | (1, 0) | (1, 1) |
C++实现：
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
int n, m, ans;
// 记录搜索的8个方向的偏移位置
int d[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,-1},{1,1},{-1,1},{1,-1}};
void DFS(vector<vector<int> > &array, int i, int j) {
array[i][j] = 0; // 状态改为0
for(int k=0;k<8;k++) // 循环搜索8个方向
if( i+d[k][0]>=0 && i+d[k][0]<n
&& j+d[k][1]>=0 && j+d[k][1]<m
&& array[i+d[k][0]][j+d[k][1]] == 1) // 搜索的下一个位置元素不越界且为1
DFS(array, i+d[k][0], j+d[k][1]);
}
int main() {
scanf("%d%d", &n, &m);
vector<vector<int> > array(n); // vector<vector<int> > 要有一个空格
for(int i=0;i<n;i++) {
array[i].resize(m); // 定义n行m列数组
}
for(int i=0;i<n;i++) {
for (int j=0;j<m;j++) {
scanf("%d",&array[i][j]); // 读取元素
}
}
for(int i=0;i<n;i++)
for (int j=0;j<m;j++)
if(array[i][j] == 1) { // 如果为1，区块数加1，然后DFS回溯
ans++;
DFS(array, i, j);
}
cout << ans; // 输出结果
return 0;
}
问题3：
给一个包含数字、字母、% 和 # 的字符串，如 3%acm#2%acm#，将 # 号前面的字母（acm）重复 % 号前面的数字（3、2）次，得到一个新字符串：acmacmacmacmacm。可以允许嵌套，如 3%g2%n##，得到 gnngnngnn（n先重复两次，然后和g组合，再重复3次）。
解题思路：
1、遍历字符串，将字符依次入栈，直到碰到 #；
2、出栈，直到碰到 %，就会得到 # 前面的字符串；
3、再出栈，直到不是数字，就会得到 % 前面的数字；
4、将 2 中得到的字符串重复 3 中得到的次数，重新压入栈。
5、直到遍历结束，栈中的字符串就是最后的答案。
注意：出栈的过程中要判断栈不为空。
按照上述解题思路，对于 3%g2%n##，栈的变化为 3%g2%n -> 3%g2% -> 3%g -> 3%gnn -> 3% -> [] -> gnngnngnn，即得到最终的答案。
C++实现：
#include <iostream>
#include <cstdio>
#include <stack>
using namespace std;
stack<string> sta; // 栈
string getstr() { // 得到 % 后 # 前的字符串
string s,t;
while(sta.empty()==false) { // 栈不为空
t = sta.top(); sta.pop();
if(t[0] == '%') break;
s = t + s;
}
return s;
}
int getint() { // 得到 % 前的数字
int num=0,res=1;
string t;
while(sta.empty()==false) { // 栈不为空
t = sta.top();
if(t[0]>='0'&&t[0]<='9') num += (t[0]-'0')*res;
else break;
sta.pop();
res*=10; // 可能多位数字
}
return num;
}
string print() { // 出栈就是最后的答案
string s,t;
while(sta.empty()==false) {
t = sta.top(); sta.pop();
s = t + s;
}
return s;
}
int main() {
string s;
cin >> s;
int len = s.size();
for(int i=0;i<len;i++) {
string tmp;
tmp += s[i];
if(s[i]>='0'&&s[i]<='9') { // 不是 # 都入栈
sta.push(tmp);
} else if(s[i]>='a'&&s[i]<='z') {
sta.push(tmp);
} else if(s[i]>='A'&&s[i]<='Z') {
sta.push(tmp);
} else if(s[i]=='%') {
sta.push(tmp);
} else {
string newstr = getstr();
int num = getint();
string t;
for(int j=0;j<num;j++) // 一次展开的字符串
t += newstr;
sta.push(t); // 展开的字符串重新压入栈
}
}
cout << print(); // 输出结果
return 0;
}
