题目:Max Ascending

By | 2012 年 12 月 14 日

问题比较简单,就是一个数组a[n] 求max(ai-aj), i<j.

从前往后扫描,记录下当前的最小值,每次计算aj – ai,然后更新这个最大值。扫描完就得到了结果,时间复杂度O(n)

<

pre>
//
// main.cpp
// MaxAscend
//
// Created by Qiu Xiangyu on 12-12-14.
// Copyright (c) 2012年 Qiu Xiangyu. All rights reserved.
//

//一个数组a[n] 求max(ai-aj), i<j

include

include

using namespace std;
int maxAscend(vector nums) {
if (nums.size() <= 1) {
return 0;
}
int ret = nums[1] – nums[0];//the result
int vmin = nums[0];//track the current min
for (int i = 1; i < nums.size(); ++i) {
int v = nums[i];
if (vmin > v) {
vmin = v;
}
if (ret < v – vmin) {
ret = v – vmin;
}
}
return ret;
}

int main(int argc, const char * argv[])
{
vector testarr = {1,4,2,5,7,0};
int md = maxAscend(testarr);
cout<<“Max difference is “<<md<<endl;
return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注