Dynamic programming - stock trading 5

Stock trading V

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 . Under the following constraints , You can do as many deals as you can （ Buy and sell a stock many times ）:

• You can't participate in multiple transactions at the same time （ You have to sell the stock before you buy it again ）.
• After sale of shares , You can't buy shares the next day ( That is, the freezing period is 11 God ).

Input format

The first line contains integers N, Represents the array length .

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

Output format

Output an integer , It means maximum profit .

Data range

1≤N≤1051≤N≤105

sample input ：

5
1 2 3 0 2

sample output ：

3

Sample explanation

The corresponding transaction status is : [ purchase , sell , Freezing period , purchase , sell ], Profit from the first transaction 2-1 = 1, Profit from the second transaction 2-0 = 2, Shared profits 1+2 = 3.

#include <bits/stdc++.h>

using namespace std;

const int N = 100010, INF = 0x3f3f3f3f;

int n;
int w[N];
int f[N][3];

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++) scanf("%d", &w[i]);
    
    f[0][0] = f[0][1] = -INF;
    f[0][2] = 0;
    
    for(int i = 1; i <= n; i ++)
    {
        f[i][0] = max((f[i - 1][2] - w[i]), f[i - 1][0]);
        f[i][1] = f[i - 1][0] + w[i];
        f[i][2] = max(f[i - 1][1], f[i - 1][2]);
    }
    
    printf("%d\n", max(f[n][1], f[n][2]));
    
    return 0;
    
}