题目 题目链接 题目链接题目解析法一：暴力枚举 此题由于是简单题，所以直接可以暴力枚举。暴力枚举的时候我们也可以考虑优化一下，比如外层枚举 $nums[i]$ 的时候，内层直接找右边的最大值。 代码如下：class Solution { public: int maximumDifference(vector<int>& nums) { int n = nums.size(); int ret = INT_MIN,mx; for(int i=0;i<n;i++){ mx = *max_element(nums.begin()+i,nums.begin()+n); if(mx>nums[i]) ret = max(ret,mx-nums[i]); } if(ret==INT_MIN)return -1; return ret; } }; 法二：dp优化 很明显，时间复杂度实际上还是 $O(n^2)$ ，我们可以通过动态规划，提前求出 $nums[i]$ 之前的最小值，然后我们就可以直接通过 $nums[i]-dp_{min}[i-1]$ 求得，此时时间复杂度被优化为了 $O(n)$ ，但空间复杂度也上升到了 $O(n)$ 。 代码如下：class Solution { public: const int maxn = 0x3f3f3f3f; int maximumDifference(vector<int>& nums) { //计算dp值 int n = nums.size(); int dp_min[n]; memset(dp_min,0x3f,sizeof(dp_min)); dp_min[0] = nums[0]; int ret = INT_MIN; for(int i=1;i<n;i++) dp_min[i] = min(dp_min[i-1],nums[i]); //得出答案 for(int i=0;i<n;i++){ if(i>0&&nums[i]>dp_min[i-1]){ ret = max(ret,nums[i]-dp_min[i-1]); } } if(ret==INT_MIN)return -1; return ret; } }; 法三：进一步优化空间复杂度 我们在 $dp$ 求解的时候发现，我们转移的状态依赖并未跨维度，而仅仅只和上一个状态 $dp[i-1]$ 相关，所以我们实际上只需要一个变量来记录 $nums[i]$ 前的最小值，故把所有的处理放到一个循环中实现即可。 代码如下：class Solution { public: int maximumDifference(vector<int>& nums) { int n = nums.size(); int ret = -1, premin = nums[0]; for (int i = 1; i < n; ++i) { if (nums[i] > premin) { ret = max(ret, nums[i] - premin); } else { premin = nums[i]; } } return ret; } };