题解 | #买卖股票的最好时机(一)#

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int prices[] = new int[n+1];
        // 注意 hasNext 和 hasNextLine 的区别
        for(int i=1;i<=n;i++){
            prices[i]=in.nextInt();
        }
        System.out.print(Main.price(prices,n));

    }
    public static long price(int prices[],int n){
        if(n==1){
            return 0;
        }
        if(n==2){
            return prices[2]-prices[1]>0?prices[2]-prices[1]:0;
        }
        long dp1[]=new long[n+1];
        dp1[0]=0;
        dp1[1]=0;
        for(int i=2;i<=n;i++){
            dp1[i]=prices[i]-prices[i-1];
        }
        long dp2[]=new long[n+1];
        dp2[0]=0;
        dp2[1]=dp1[1];
        long max_value=dp2[1];
        for(int i=2;i<=n;i++){
            dp2[i]=Math.max(dp2[i-1]+dp1[i],dp1[i]);
            if(dp2[i]>max_value){
                max_value=dp2[i];
            }
        }
        return max_value;
    }
}