Online Judge

【DidaOJ】8-严格递增连续子段

文章字数：713

问题描述

问题分析

会有一些不容易想到的边界情况。

比较容易想到的是遍历数组，计算如果不允许修改那么能拿到的最大长度是多少。

而修改某个数字能得到最大长度，说明修改这个数字能把左边的长度和右边的长度连起来。

顺着这个思路，就可以思考边界情况，判断出来能否连起来。

为了O(N)复杂度得到长度，可以分别计算以i结尾的最大长度和以i开头的最大长度（反向遍历即可），这样就可以比较方便的在遍历时聚焦i能否通过修改拼接左右两部分。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

#include <iostream>

int a[100020];
int endAns[100020]; // 以i结尾的最长递增子序列
int startAns[100020]; // 以i开头的最长递增子序列

int main()
{
    int T;
    std::cin >> T;
    while (T--)
    {
        int n;
        std::cin >> n;
        for (int i = 0; i < n; ++i)
        {
            std::cin >> a[i];
        }

        int tempAns = 0;
        for (int i = 0; i < n; ++i)
        {
            if (i == 0 || a[i] > a[i - 1])
            {
                ++tempAns;
            }
            else
            {
                tempAns = 1;
            }
            endAns[i] = tempAns;
        }
        tempAns = 0;
        for (int i = n - 1; i >= 0; --i)
        {
            if (i == n - 1 || a[i] < a[i + 1])
            {
                ++tempAns;
            }
            else
            {
                tempAns = 1;
            }
            startAns[i] = tempAns;
        }

        // for (int i = 0; i < n; ++i)
        // {
        //     std::cout << endAns[i] << " ";
        // }
        // std::cout << std::endl;
        // for (int i = 0; i < n; ++i)
        // {
        //     std::cout << startAns[i] << " ";
        // }
        // std::cout << std::endl;

        int ans = 1;
        for (int i = 0; i < n; ++i)
        {
            if (i == 0 && i == n - 1)
            {
                // 只有一个数
                ans = 1;
            }
            else if (i == 0)
            {
                // 考虑将第一个数修改为比第二个数小的数
                ans = std::max(ans, startAns[i + 1] + 1);
            }
            else if (i == n - 1)
            {
                // 考虑将最后一个数修改为比倒数第二个数大的数
                ans = std::max(ans, endAns[i - 1] + 1);
            }
            // 判断修改一个数能否让endAns与startAns接上
            else if (a[i - 1] + 1 < a[i + 1])
            {
                ans = std::max(ans, endAns[i - 1] + startAns[i + 1] + 1);
            }
            else
            {
                // 否则至少能接上其中一个
                ans = std::max(ans, endAns[i - 1] + 1);
                ans = std::max(ans, startAns[i + 1] + 1);
            }
        }
        std::cout << ans << std::endl;
    }
    return 0;
}

题目地址：【DidaOJ】[8]严格递增连续子段

加载中...