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

import java.io.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int len = Integer.parseInt(br.readLine());
        String[] s = br.readLine().split(" ");
        int [] arr = new int [len];
        for(int i=0; i<len;i++){
            arr[i] = Integer.parseInt(s[i]);
        }

        //处理
        //可以进行多次买卖是难点
        //1 2 4 4 5 的情况
        //***********方法一 */
        //寻找所有的上涨空间
        // int current = arr[0];
        // int sum=0;
        // for(int i=1;i<len;i++){
        //     if(arr[i]>arr[i-1]){
        //         sum +=arr[i]-arr[i-1];
        //     }
        // }
        // System.out.println(sum);
        //*******方法二 */
        //这种一维的线性的统一使用线性dp分析情况解决
        //dp[i][0]表示此时手上无股票 dp[i][1]表示此时手上有股票
        int [][] dp = new int [len+1][2];
        dp[0][1] = -arr[0];
        for(int i=1;i<=len;i++){
            //可能会疑惑会不会中间有段时间损失后来最大不会 一种贪心的思路3-1-5和3-5一样
            //每时每刻都取利润最大即可
            //手上没股票可能在这一轮卖出 或者这前一直没有
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+arr[i-1]);
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-arr[i-1]);
        }
        System.out.println(dp[len][0]);
    }
}