Stock trading 4

Stock trading IV

Given a length of N Array of , The... In the array i A number indicates that a given stock is on the i Sky price .

Design an algorithm to calculate the maximum profit you can get , You can do at most k transaction .

Be careful ： You can't participate in multiple transactions at the same time （ You have to sell the stock before you buy it again ）. One buy and one sell is one transaction .

Input format

The first line contains integers N and k, Indicates the length of the array and the maximum number of transactions you can complete .

The second line contains N No more than one. 10000 The positive integer , Represents a complete array .

Output format

Output an integer , It means maximum profit .

Data range

1≤N≤1051≤N≤105,
1≤k≤1001≤k≤100

sample input 1：

3 2
2 4 1

sample output 1：

2

sample input 2：

6 2
3 2 6 5 0 3

sample output 2：

7

Sample explanation

Examples 1： In the 1 God ( Stock price = 2) Buy when , In the 2 God ( Stock price = 4) Sell when , The exchange will make a profit = 4-2 = 2 .

Examples 2： In the 2 God ( Stock price = 2) Buy when , In the 3 God ( Stock price = 6) Sell when , The exchange will make a profit = 6-2 = 4 . And then , In the 5 God ( Stock price = 0) Buy when , In the 6 God ( Stock price = 3) Sell when , The exchange will make a profit = 3-0 = 3 . Total profit 4+3 = 7.

#include <bits/stdc++.h>

using namespace std;

const int N = 100010, M = 110;

int n, m;
int w[N];
int f[N][M][2];

int main()
{
    cin >> n >> m;
    
    for(int i = 1; i <= n; i ++) cin >> w[i];
    
    memset(f, -0x3f, sizeof f);
    for(int i = 0; i <= n; i ++) f[i][0][0] = 0;
    
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
        {
            f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j][1] + w[i]);
            f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - w[i]);
        }
        
    int res = 0;
    for(int i = 1; i <= m; i ++) res = max(res, f[n][i][0]);
    
    printf("%d\n", res);
    
    return 0;
}