AcWing 1055. 股票买卖 II 数学归纳法证明
原题链接
简单
作者:
季之秋
,
2021-03-17 21:31:38
,
所有人可见
,
阅读 288
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int p[]=new int[100010];
for(int i=0;i<n;i++) p[i]=sc.nextInt();
int sum=0;
for(int i=1;i<n;i++)
if(p[i]>p[i-1]) sum+=p[i]-p[i-1];
//拆分原则:
// 对于最优解的任一个区间 p[i]-p[j],之间的数 p[k]<=p[j]&&p[k]>=p[i];否则可以找到更优的解
//我们找到p[i -- j]的最大值p[k] 拆分为p[i]-p[k] 和 p[k]-p[j];
//以此类推到两个相邻区间 p[i]-p[i+1],所以最优解拆分若干个相邻的区间
//并且最优解区间一定要>0 否则的话我们不选这个区间就可以找出更优的解
System.out.println(sum);
}
}