链接：https://www.nowcoder.com/questionTerminal/bd891093881d4ddf9e56e7cc8416562d?orderByHotValue=0&page=1&onlyReference=false
来源：牛客网

读入一个字符串str，输出字符串str中的连续最长的数字串

输入描述:

个测试输入包含1个测试用例，一个字符串str，长度不超过255。

输出描述:

在一行内输出str中里连续最长的数字串。

示例1

输入

abcd12345ed125ss123456789

输出

123456789

思路1： 利用常规手段，从起始位置开始寻找，找到数字串之后存下来，和保存的最长数字串长度进行比较，保留最大的，直到超过字符串的size。代码较为简单，就不贴出来了。

思路2：利用动态规划实现

开辟二维数组进行存放当前字符串中最长数字串的个数，找到最长的数字串之后将其截取出来。

代码及注释如下：

#include <iostream>
#include <vector>
using namespace std;


int main()
{
	string s;
	while (getline(cin,s))
	{
		int len = s.size();
		vector<vector<int>> vv;
		vv.resize(len);
		for (int i = 0; i<len; i++)
		{
			vv[i].resize(len);
		}
        
        //第一个字符是数字就将其标记为1，否则是0
		if (isdigit(s[0]))
			vv[0][0] = 1;
		else
			vv[0][0] = 0;

		int max = vv[0][0];
		int index = 0;

        //只走对角线
		for (int i = 1; i<vv.size(); i++)
		{
			for (int j = i; j<i + 1; j++)
			{
				if (isdigit(s[i]))//当前字符是数字，那么截止当前位置的数字串长度就是1+前面的长度
					vv[i][j] = vv[i - 1][j - 1] + 1;
				else//当前不是数字直接将该位置置0
					vv[i][j] = 0;

				if (vv[i][j] > max)//每次看是否需要更新max
				{
					max = vv[i][j];
					index = i - max + 1;//记录当前数字串的起始下标
				}
			}
		}
        //截取最长的字符串
		string ret = s.substr(index, max);
		cout << ret << endl;
	}
	return 0;
}