问题 B: 预定货物
传统题
1.000s
时间限制
256MB
内存限制
4 提交
3 解决
【题目描述】
题目描述
为了赚取零花钱，小爱决定趁暑假去外地订购学习用品，然后转手卖掉以赚取中间差价。受天气和心情影响，学习用品的进价和售价都在不断改变，具体而言，暑假一共有n
天，其中第i天订购一套学习用品的进价是ai
，第i天转手卖掉一套学习用品的售价是bi
。由于订货路途也会费时，如果小爱在第i天订购了学习用品，那么她只能在第i+1
天到第n天中的任何一天进行出售。
小爱总共只打算订购一套学习用品，并在适当的时机出售以赚取尽可能多的差价。现在小爱想知道，自己能赚取到的最大差价是多少。
输入格式
第一行包含一个正整数n，表示暑假的天数。
第二行包含n个正整数，其中第i个数ai
表示第i天订购一套学习用品的进价。
第三行包含n个正整数，其中第i个数bi
表示第i天卖掉一套学习用品的售价。
输出格式
输出一行一个正整数，表示小爱能赚取到的最大差价。如果小爱在任何时机订购并在之后出售都没有办法赚到钱，请输出0。
数据范围
对于30%
的数据，保证1≤n≤200
。
对于60%的数据，保证1≤n≤2000
。
对于90%的数据，保证1≤n≤200,000
。
对于100%的数据，保证1≤n≤2,000,000
，1≤ai,bi≤1,000,000
。
样例数据
输入:
3
1 2 3
6 5 4
输出:
4
说明:
第一天1块钱买，第二天5块钱卖，赚取4元