链接：https://ac.nowcoder.com/acm/contest/20323/D

来源：牛客网

题目描述

白云已经建立了n家店铺，数量从1到n不等。

白兔想按从1到n的顺序参观这些商店。

编号为i的商店有一个价格a[i]，表示大白兔在第i家商店可以花费a[i]美元购买产品或销售产品以获得a[i]美元。

产品太重，大白兔一次只能吃一种产品。

在参观了所有的商店之后，白兔想知道最大利润。

另外，白兔想知道在获得最大利润的同时，交易的最少数量。

请注意，白兔最初拥有无限的金钱。

输入描述:

第一行包含一个整数T（0<T<=5），表示测试用例的数量。

在每个测试用例中，第一行中有一个整数n（0<n<=100000），表示存储的数量。

对于下一行，范围[02147483648]中有n个整数，表示[1..n]。

输出描述:

对于每个测试用例，打印一行包含2个整数，表示最大利润和最小交易数。

思路和心得

（一）dp

1.和力扣上，股票的最大收益是一样的

python3代码

T = int(input())
for _ in range(T):
    n = int(input())
    nums = [int(x) for x in input().split()]
    
    dp = [[0, 0] for _ in range(n)]
    dp[0][0] = 0
    dp[0][1] = -nums[0]
    step = [[0, 0] for _ in range(n)]
    step[0][1] = 1
    for i in range(1, n):
        if dp[i - 1][1] + nums[i] > dp[i - 1][0]:
            dp[i][0] = dp[i - 1][1] + nums[i]
            step[i][0] = step[i - 1][1] + 1
        else:
            dp[i][0] = dp[i - 1][0]
            step[i][0] = step[i - 1][0]
        if dp[i - 1][0] - nums[i] > dp[i - 1][1]:
            dp[i][1] = dp[i - 1][0] - nums[i]
            step[i][1] = step[i - 1][0] + 1
        else:
            dp[i][1] = dp[i - 1][1]
            step[i][1] = step[i - 1][1]
    print("{} {}".format(dp[n - 1][0], step[n - 1][0]))
    
    

c++代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <assert.h>

using namespace std;

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int T;    cin >> T;
    for (int _ = 0; _ < T; _ ++)
    {
        int n;    cin >> n;
        int nums[n];
        for (int i = 0; i < n; i ++){
            cin >> nums[i];
        }
        
        long long dp[n][2];
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 0LL;
        dp[0][1] = -nums[0];
        int step[n][2];
        memset(step, 0, sizeof(step));
        step[0][0] = 0;
        step[0][1] = 1;
        
        for (int i = 1; i < n; i ++)
        {
            if (dp[i - 1][1] + nums[i] > dp[i - 1][0])
            {
                dp[i][0] = dp[i - 1][1] + nums[i];
                step[i][0] = step[i - 1][1] + 1;
            }
            else
            {
                dp[i][0] = dp[i - 1][0];
                step[i][0] = step[i - 1][0];
            }
            
            if (dp[i - 1][0] - nums[i] > dp[i - 1][1])
            {
                dp[i][1] = dp[i - 1][0] - nums[i];
                step[i][1] = step[i - 1][0] + 1;
            }
            else
            {
                dp[i][1] = dp[i - 1][1];
                step[i][1] = step[i - 1][1];
            }
        }
        
        cout << dp[n - 1][0] << ' ' << step[n - 1][0] << endl;
    }
   
    return 0;
}

java代码

import java.util.*;
import java.io.*;

public class Main
{
    public static void main(String [] args) throws Exception
    {
        BufferedReader BR = new BufferedReader(new InputStreamReader(System.in));
        String [] line1 = BR.readLine().split(" ");
        int T = Integer.parseInt(line1[0]);
        for (int ee = 0; ee < T; ee ++)
        {
            String [] line2 = BR.readLine().split(" ");
            int n = Integer.parseInt(line2[0]);
            
            int [] nums = new int [n];
            String [] line3 = BR.readLine().split(" ");
            for (int i = 0; i < n; i ++){
                nums[i] = Integer.parseInt(line3[i]);
            }
            
            long [][] dp = new long [n][2];
            dp[0][0] = 0L;
            dp[0][1] = -nums[0];
            int [][] step = new int [n][2];
            step[0][0] = 0;
            step[0][1] = 1;
            for (int i = 1; i < n; i ++)
            {
                if (dp[i - 1][1] + nums[i] > dp[i - 1][0])
                {
                    dp[i][0] = dp[i - 1][1] + nums[i];
                    step[i][0] = step[i - 1][1] + 1;
                }
                else
                {
                    dp[i][0] = dp[i - 1][0];
                    step[i][0] = step[i - 1][0];
                }
                
                if (dp[i - 1][0] - nums[i] > dp[i - 1][1])
                {
                    dp[i][1] = dp[i - 1][0] - nums[i];
                    step[i][1] = step[i - 1][0] + 1;
                }
                else
                {
                    dp[i][1] = dp[i - 1][1];
                    step[i][1] = step[i - 1][1];
                }
            }
            
            System.out.println(dp[n - 1][0] + " " + step[n - 1][0]);
            
        }
    }
}