如何从纯数字串生成非连续4位最大子序列并求解最大值？

需求 #

给定一个混有字母和数字的字符串，先移除所有字母得到纯数字串，再找出其中长度为4、保持原有顺序的非连续子序列的最大值。

示例 #

输入：24d5n4r05f704n652z393
处理后纯数字串：245405704652393
输出：7693

当前代码问题 #

现有代码只能生成连续子串（如2、24、245），无法生成符合要求的非连续子序列（如254、440），因此无法正确求解最大值。原代码如下：

#include <string>
#include <vector>
#include <iostream>

using namespace std;

ifstream fi;
ofstream fo;

void tlw(string &s){  //将大写字母转换为小写
    for(int i=0; i<s.length(); i++){
        if(s[i]>='A'&&s[i]<='Z'){
            s[i]=tolower(s[i]);
        }
    }
}
void duyet(string s, int n){  //生成子串并比较最大值
    int max = 0, dem;
    string new_s;
    vector<string> a;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            new_s = s.substr(i,j-i+1);   //此处为需要修改的核心部分
            if (new_s.length() == 4){
                int dem = stoi(new_s);
                if (max<dem){
                    max = dem;
                }
            }
        }
    }
    fo<<max;
}
void xuli(string s, int n){     //问题处理函数
    tlw(s);
    int e = 0;
    for(int i=0; i<n; i++){
        if (s[i] >= 'a' && s[i] <= 'z'){
            e = i; 
            s.erase(e,1);
        }
    }
    duyet(s,s.length());
}
int main(){
    fi.open("dctn.inp");fo.open("dctn.out");
    string s;
    fi>>s; int n = s.length();
    xuli(s,n);
    fi.close();fo.close();
}

修改方案 #

1. 修复字母移除逻辑 #

原代码删除字母时会因为字符串长度变化导致索引错位，改用直接筛选数字的方式更可靠：

void xuli(string s, int n){     
    tlw(s);
    string num_str;
    // 只保留数字字符
    for(char c : s){
        if(isdigit(c)){
            num_str += c;
        }
    }
    duyet(num_str, num_str.length());
}

2. 重写子序列生成逻辑 #

要生成长度为4的非连续子序列，需要遍历所有满足i < j < k < l的索引组合，提取对应字符拼接后比较最大值，修改duyet函数：

void duyet(string s, int n){  
    int max_val = 0;
    // 遍历所有合法的4元非连续索引组合，确保顺序i<j<k<l
    for(int i=0; i < n-3; i++){
        for(int j=i+1; j < n-2; j++){
            for(int k=j+1; k < n-1; k++){
                for(int l=k+1; l < n; l++){
                    string sub = string(1, s[i]) + s[j] + s[k] + s[l];
                    int num = stoi(sub);
                    if(num > max_val){
                        max_val = num;
                    }
                }
            }
        }
    }
    fo<<max_val;
}

说明 #

• 字母移除逻辑改为直接筛选数字，避免了删除字符后的索引错位问题，代码更简洁稳定。
• 四层循环遍历所有符合要求的4位非连续子序列，确保生成的子序列保持原数字顺序，通过逐一比较得到最大值。

内容的提问来源于stack exchange，提问作者Lanju