c435 - MAX ! MAX ! MAX !

🔗 前往 ZeroJudge 原題

題目描述

題目要求找出數列中，滿足 i < j 的條件下，a[i] - a[j] 的最大值。

解題思路

題目可以使用貪心法解決。遍歷數列，維護一個 max 變數，記錄目前遇到的最大值。對於每個元素 n，如果 n 大於 max，則更新 max。否則，計算 max - n，如果這個差值大於目前的 ans，則更新 ans。最終 ans 就是所求的最大差值。

複雜度分析

• 時間複雜度: O(n)
• 空間複雜度: O(1)

程式碼

#include <stdio.h>
int  main(){
	int n,max=0,ans=0;
	scanf("%d",&n);
	while(scanf("%d",&n)>0){
		if(n>max)
			max=n;
		else if(max-n>ans)
			ans=max-n;
	}
	printf("%d",ans);
}