【网易2019秋招在线笔试】算法第二题参考思路

题目：在一个最大长度200000的数组中，分别求出长度从1到n的子序列中最大值的最小值
样例（自己写的）：
输入：
6
1 8 7 5 4 2
输出：
1 4 5 7 8 8

简单来说，就是把一个数组进行连续子序列的划分，从长度为1的子序列开始划分，每次划分子序列后，求出每个子序列的最大值，再求出所有这些最大值中最小的那个，一直到长度为n的子序列（序列本身）。

这题一开始把我看绕了，其实就是一道标准的DP题，然而我最后做的这题，考完才写出来。。。这次笔试基本是按照最差的答题顺序来的，估计跪了。

状态转移方程可以这样想出来：

设dp[j][i]是从数组第j个数字开始的长度为i的子序列的最大值，当长度i=0（实际长度应该为1，从0开始方便些）时，dp[j][0]等于数字本身num[j]，从i=1开始，dp[j][i]的长度等于MAX(dp[j][i-1], dp[j+1][i-1])也就是前后相邻的两个长度为i-1的子序列最大值中的最大值。
这题要求的是同一划分长度下所有最大值的最小值，所以在计算dp数组的同时还要计算这个值是否为当前划分长度的最小值，于是定义一个min数组，长度100000，先初始化成最大数值,每次计算dp[j][i]的时候与min[i]比较哪个值更小，一趟下来就能得到最小值了。

我的思路大概就是这样，欢迎大家讨论。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <algorithm>
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define INF 0x7FFFFFFF
using namespace std;
int num[100000] = { 0 };
int (*dp)[100000];
int main()
{
    int n;
    int min[100000] = { 0 };
    scanf("%d", &n);
    dp = (int (*)[100000])malloc(n * 100000 * sizeof(int));
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &num[i]);
        min[i] = INF;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n - i; j++)
        {
            if (i == 0)
            {
                dp[j][0] = num[j];
            }
            else
            {
                dp[j][i] = MAX(dp[j][i - 1], dp[j + 1][i - 1]);
            }
            if (dp[j][i] < min[i])
            {
                min[i] = dp[j][i];
            }
            i = i;
        }
    }
    for (int i = 0; i < n; i++)
    {
        if (i>0)
        {
            printf(" ");
        }
        printf("%d", min[i]);
    }
    printf("\n");
    return 0;
}