买卖股票的最好时机(一)

简单贪心

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int p[N];

int main() 
{
    int n; cin >> n;
    for(int i = 0; i < n; i++) cin >> p[i];

    int ans = 0, mi = 1e5;
    for(int i = 0; i < n; i++)
    {
        ans = max(ans, p[i] - mi);
        mi = min(mi, p[i]);
    }
    cout << ans << '\n';
}

import sys

def main():

    n = int(sys.stdin.readline().strip())

    arr = list(map(int, sys.stdin.readline().strip().split(' ')))

    dp = [0 for i in range(n)]
    dp[0] = arr[0]

    # 从左边顺延遇到的最小的值
    for i in range(1, n):
        if arr[i] > dp[i-1]:
            dp[i] = dp[i-1]
        else:
            dp[i] = arr[i]

    # print(dp)
    # 计算从右边减去左边最小的值
    res = 0
    for i in range(n-1, -1, -1):
        res = max(res, arr[i] - dp[i])

    print(res)

main()

import java.util.*;
public class Main{
    public static void main(String[] args){
        //处理输入输出
        Scanner scan=new Scanner(System.in);
        String nStr=scan.nextLine();//输入一个正整数n 读取第一行数据
        int n=Integer.valueOf(nStr);//将String变int
        String numsStr=scan.nextLine();//输出n个正整数  读取第二行数据
        String[] numsStrList=numsStr.split(" ");
        int[] nums=new int[numsStrList.length];
        for(int i=0;i<nums.length;i++){  //String[]变int[]
            nums[i]=Integer.valueOf(numsStrList[i]);
        }
        //核心代码模式
        //if(nums==null||nums.length==0) {
        if(nums.length==1){
            System.out.println(0);
            return;
        }
        int[][] dp=new int[nums.length][2];
        //0表示持有 1表示不持有
        dp[0][0]=-nums[0];
        dp[0][1]=0;
        for(int i=1;i<nums.length;i++){
            dp[i][0]=Math.max(dp[i-1][0],-nums[i]);
            dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]+nums[i]);
        }
        System.out.println(dp[nums.length-1][1]) ;
    }
}

package main

import (
    "fmt"
    "math"
)

func main() {
    var n int
    fmt.Scan(&n)
    min:=math.MaxInt32
    ans:=0
    var x int
    for n>0{
        fmt.Scan(&x)
        if x-min>ans{
            ans=x-min
        }
        if x<min{
            min=x
        }
        n--
    }
    fmt.Print(ans)
}

import java.util.Scanner;

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

fun main(){
    //dp(i) = Max(dp(i-1) + price[i-1] - price[i-2], price[i-1]-price[i-2])
    //max(n) = max(dp(2) .. dp(n))
    var maxSubSum = 0;
    var n = readLine()!!.toInt();
    var strArray = readLine()!!.split(" ");
    var intArray = IntArray(size = n , init = { it -> strArray[it].toInt() })
    var dp = IntArray(size = n+2, init = { -200000 })
    var begin=-1
    var end=-1

    dp[1] = 0
    if(n >= 2){
        for(i in 2 .. intArray.size){
            if(dp[i-1] + intArray[i-1] - intArray[i-2] > intArray[i-1] - intArray[i-2] ) {
                dp[i] = dp[i-1] + intArray[i-1] - intArray[i-2];
                end = i;
            } else {
                dp[i] =   intArray[i-1] - intArray[i-2] ;
                begin=i-2;
                end = i-1;
            }
        }
    }
    for(dpValue in dp){
        if(maxSubSum < dpValue){
            maxSubSum = dpValue;
        }
    }

    //println( "begin=${begin} end=${end}" );
    println(maxSubSum);
}

#include<bits/stdc++.h>
using namespace std;
int maxProfit(vector<int>&prices){
    int n=prices.size();
    //dp[i]表示第i天获得的最大利润
    vector<int>dp(n);
    dp[0]=0;
    int minPrice=prices[0];
    for(int i=1;i<n;i++){
        minPrice=min(minPrice,prices[i]);
        //两种状态：今天不卖，今天卖
        dp[i]=max(dp[i-1],prices[i]-minPrice);
    }
    return dp[n-1];
}
int main(){
    int n;cin>>n;
    vector<int>Prices(n);
    for(int i=0;i<n;i++) cin>>Prices[i];
    cout<<maxProfit(Prices);
}