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

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);
        String str1=scan.nextLine();
        String[] str11=str1.split(" ");
        int[] NandK=new int[str11.length];
        for(int i=0;i<str11.length;i++){
            NandK[i]=Integer.valueOf(str11[i]);
        }
        int n=NandK[0];
        int k=NandK[1];
        String str2=scan.nextLine();
        String[] str22=str2.split(" ");
        int[] nums=new int[str22.length];
        for(int i=0;i<nums.length;i++){
            nums[i]=Integer.valueOf(str22[i]);
        }
       
        //最多K笔交易
        if(nums.length==1){
            System.out.println(0);
            return;
        }
        int[][] dp=new int[nums.length][2*k+1];//2笔交易5个状态
       /* dp[0][0]=0;  //奇偶，偶数初始化为0，奇数初始化为-nums[0]
        dp[0][1]=-nums[0];
        dp[0][2]=0;
        dp[0][3]=-nums[0];
        dp[0][4]=0;  */
        //初始化完毕
        for(int i=0;i<2*k+1;i++){  //注意这里i的取值范围为0 ~（2*k+1）
            if(i%2==0){
                dp[0][i]=0;
            }else{
                dp[0][i]=-nums[0];
            }
        }
        for(int i=1;i<nums.length;i++){
            for(int p=1;p<2*k+1;p++){
                if(p%2==1){
                    dp[i][p]=Math.max(dp[i-1][p],dp[i-1][p-1]-nums[i]);//买入
                }else{
                    dp[i][p]=Math.max(dp[i-1][p],dp[i-1][p-1]+nums[i]);//卖出
                }
            }
        }
        System.out.println(dp[nums.length-1][2*k]);
    }
}

import java.util.Arrays;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int k = in.nextInt();
            int[] price = new int[n];
            for (int i = 0; i < n; i++) price[i] = in.nextInt();
            int sum = 0;
            int[] buy = new int[k + 1];
            int[] sell = new int[k + 1];
            Arrays.fill(buy, Integer.MIN_VALUE);
            Arrays.fill(buy, Integer.MIN_VALUE);
            for (int i = 0; i < n; i++) {
                for (int j = 1; j <= k; j++) {
                    buy[j] = Math.max(buy[j], sell[j - 1] - price[i]);
                    sell[j] = Math.max(sell[j], buy[j] + price[i]);
                }
            }
            System.out.println(sell[k]);
        }
    }
}

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> vi(n, 0);
    for (int i = 0; i < n; ++i) {
        cin >> vi[i];
    }
    int res = 0;
    vector<pair<int, int>> dp(k+1);
    dp[0] = make_pair(0, 0);
    for (int j = 1; j <= k; ++j) {
            dp[j] = make_pair(-vi[0], 0);
    }
    for (int i = 1; i < n; ++i) {
        for (int j = 1; j <= k; ++j) {
            dp[j].first = max(dp[j].first, dp[j-1].second -vi[i]);
            dp[j].second = max(dp[j].second, vi[i] + dp[j].first);
        }
    }
    res = dp[k].second;
    cout << res;
}
// 64 位输出请用 printf("%lld")

#include<bits/stdc++.h>
using namespace std;
int maxProfit(vector<int>&prices,int k){
    int n=prices.size();
    k=min(k,n/2);
    //2k+1种状态
    vector<int>buy(k+1);
    vector<int>sell(k+1);
    buy[0]=-prices[0];
    sell[0]=0;
    for(int i=1;i<=k;i++){
        buy[i]=sell[i]=INT_MIN/2;
    }
    for(int i=1;i<n;i++){
        buy[0]=max(buy[0],sell[0]-prices[i]);
        for(int j=1;j<=k;j++){
            buy[j]=max(buy[j],sell[j]-prices[i]);
            sell[j]=max(sell[j],buy[j-1]+prices[i]);
        }
    }
    return *max_element(sell.begin(),sell.end());
}
int main(){
    int n,k;cin>>n>>k;
    vector<int>prices(n);
    for(int i=0;i<n;i++)cin>>prices[i];
    cout<<maxProfit(prices,k);
}