SDMU OJ＃P19. Stock trading

Description

Qiqi is a stock market enthusiast , Obsession and stock speculation all day , But due to the poor mathematics of seven seven , I need you to help him figure out the maximum profit from stock speculation . Now let's give a length of N  Array of , The... In the array i A number indicates that a given stock is on the i Sky price . If only one transaction is allowed to be completed at most （ Buy and sell a stock ）, Design an algorithm to calculate the maximum profit that 77 can get . Note that you can't sell shares before you buy them （ If there is no transaction , The biggest profit is 0）. Because Qiqi is a very good stock trader , The final profit of 77 is the original profit 100 times , If the final profit of 77 is less than 1e18, Then output the profit obtained , Otherwise output “fa cai le!”.

Input

The first line contains integers NNN, Represents the array length . The second line contains NNN No more than one. 1e18 The positive integer , Represents a complete array .(1<=N<=100000)

Output

If the final profit of 77 is less than 1e18, Then output the profit obtained , Otherwise output “fa cai le!”.

Sample

Input 1

5
46 49 49 35 48

Output 1

1300

Input 2

2
1 1000000000000000000

Output 2

fa cai le!

Hint

The time limit ：1000ms

Memory limit ：65536KiB

This problem is nothing more than finding the maximum difference , There are two ways of thinking ：

1. greedy ：

j>i, Find the largest of all the intervals a[j]-a[i], Finally, output according to the requirements of the topic , The reference codes are as follows ：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 long long  a[100010];
 4 int n;
 5 long long ans; 
 6 int main()
 7 {
 8     ios::sync_with_stdio(false);
 9     cin>>n;
10     for(int i=1;i<=n;i++)
11     cin>>a[i];
12         for(register int i=1;i<=n;i++) 
13         {
14             for(register int j=i+1;j<=n;j++)
15             {
16                 ans=max(ans,a[j]-a[i]);
17             }
18         }
19         if(ans*100<1e18)
20         cout<<ans*100;
21         else
22         cout<<"fa cai le!";
23     return 0;
24 }

The next method is dp, We let dp【i】 Before presentation i The smallest stock value in days , It is equivalent to finding the starting point ,

Ask for maximum profit , namely a[j]-a[i] The biggest and i < j. If we can know before j The minimum of the elements , You can find the starting point of buying stocks . So make dp[i] Before presentation i The minimum of the elements , We can get such a state transition equation ：
dp[1] = a[1],dp[i] = min(a[i], dp[i-1]).
that a[i] - dp[i] It represents the former i The maximum profit of the elements . Let's enumerate i, Find the biggest i bring a[i]-dp[i] The biggest one is .

The reference codes are as follows ：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 long long dp[100010];// front i The smallest of the elements  
 4 long long a[100010];
 5 int n;
 6 long long ans;
 7 int main()
 8 {
 9     ios::sync_with_stdio(false);
10     cin>>n;
11     for(int i=1;i<=n;i++)
12     cin>>a[i];
13     dp[1]=a[1];// initialization  
14     for(int i=2;i<=n;i++)
15     {
16         dp[i]=min(dp[i-1],a[i]);// Transfer equation  
17         ans=max(ans,a[i]-dp[i]);// At present ans Who is the difference between the value of the current stock and the minimum stock value , Start enumeration  
18     }
19     if(ans*100<1e18)
20     cout<<ans*100;
21     else
22     cout<<"fa cai le!";
23     return 0;
24 }