详细题解可以查看我的CSDN AcWing 3748. 递增子串 差分思想 c++和Java实现

本题要求以第 i 位置为结尾的最长严格递增序列的长度，可以采用差分的思想。

当后一个字母比前一个字母大（严格递增）时，二者做差则必为正数；

而当前一个字母比后一个字母小或者相等时，二者做差则会小于等于 0；

所以一个严格递增序列的长度为从 i 位置向前找差连续为正数的长度加一（加一是计算起点）；

此时，如果我们从前往后找，每次遇到负数或者0，就将长度初始化为1（即只有自己递增），因为对于后面的字母来说，负数或者0之前位置的字母必然不递增；而遇到正数则将长度加一。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
public class Main {
    public static void main(String[] args) throws IOException {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int t = in.nextInt();
        int n = 0;
        char[] ch;
        int[] d;
        int cnt = 1;
        for(int i = 1; i <= t; i++) {
            n = in.nextInt();
            ch = in.next().toCharArray();
            d = new int[n];
            for(int j = 1; j < n; j++) {
                d[j] = ch[j] - ch[j - 1];
            out.print("Case #" + i + ": 1");
            cnt = 1;
            for(int j = 1; j < n; j++) {
                if(d[j] > 0) cnt++;
                else cnt = 1;
                out.print(" " + cnt);
            out.println();
        out.flush();
    public static class InputReader {
        BufferedReader reader;
        StringTokenizer tokenizer;
        public InputReader(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
        public String next() throws IOException {
            while(tokenizer == null || !tokenizer.hasMoreTokens()) {
                tokenizer = new StringTokenizer(reader.readLine());
            return tokenizer.nextToken();
        public int nextInt() throws IOException {
            return Integer.parseInt(next());
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 +10;
int main()
    int t, n;
    cin >> t;
    string s;
    int d[N];
    int cnt = 1;
    for(int i = 1; i <= t; i++)
        cin >> n;
        cin >> s;
        for(int j = 1; j < n; j++)
            d[j] = s[j] - s[j - 1];
        cout << "Case #" << i << ": 1";
        cnt = 1;
        for(int j = 1; j < n; j++)
            if(d[j] > 0) cnt++;
            else cnt = 1;
            cout << " " << cnt;
        cout << endl;
    return 0;