顺序最大差值问题

问题描述: 给一个长度为n的整数序列, A0 - An, 找两个整数Ai, Aj(i < j), 使得Ai - Aj最大, 这里有个最优方案.

枚举所有的j, 我们只需要维护小于j的最大的Ai就可以了, 效率可以达到O(n)

int maxi = A[0], ans = 0;

for (int j = 1; j < n; j++) {

    ans = max(ans, maxi - A[j]);

    maxi = max(maxi, A[j]);

}

同理, 这类问题推广一下, 凡是涉及到顺序当中, 需要最大/最小值的, 都可以使用这种方式.