PTA A_1101 Quick Sort

798236606

题目链接:https://pintia.cn/problem-sets/994805342720868352/problems/994805366343188480

解：
递推法

#include <stdio.h>

int nums[100010];
int l_max[100010];
int r_min[100010];
int candi[100010];

int main(void)
{
        int i, n, count = 0;
        
        scanf("%d", &n);
        for (i = 0; i < n; i++)
                scanf("%d", nums + i);
                
        l_max[0] = nums[0];
        r_min[n - 1] = nums[n - 1];
        
        for (i = 1; i < n; i++)
                l_max[i] = (nums[i] > l_max[i - 1]) ? nums[i] : l_max[i - 1];

        for (i = n - 2; i >= 0; i--)
                r_min[i] = (nums[i] < r_min[i + 1]) ? nums[i] : r_min[i + 1];
                
        for (i = 0; i < n; i++)
                if ((nums[i] == l_max[i]) && (nums[i] == r_min[i]))
                        candi[count++] = nums[i];
        
        printf("%d\n", count);                
        for (i = 0; i < count; i++)
        {
                printf("%d", candi[i]);
                
                if (i + 1 < count)
                        putchar(' ');
        }                
        putchar('\n');
                        
        return 0;
}