跳转至

2291. 最大股票收益 🔒

题目描述

给你两个下标从 0 开始的数组 present 和 future ，present[i] 和 future[i] 分别代表第 i 支股票现在和将来的价格。每支股票你最多购买 一次 ，你的预算为 budget 。

求最大的收益。

 

示例 1：

输入：present = [5,4,6,2,3], future = [8,5,4,3,5], budget = 10
输出：6
解释：你可以选择购买第 0,3,4 支股票获得最大收益：6 。总开销为：5 + 2 + 3 = 10 , 总收益是: 8 + 3 + 5 - 10 = 6 。

示例 2：

输入：present = [2,2,5], future = [3,4,10], budget = 6
输出：5
解释：你可以选择购买第 2 支股票获得最大收益：5 。总开销为：5 , 总收益是: 10 - 5 = 5 。

示例 3：

输入：present = [3,3,12], future = [0,3,15], budget = 10
输出：0
解释：你无法购买唯一一支正收益股票 2 ，因此你的收益是 0 。

 

提示：

  • n == present.length == future.length
  • 1 <= n <= 1000
  • 0 <= present[i], future[i] <= 100
  • 0 <= budget <= 1000

解法

方法一：动态规划

我们定义 $f[i][j]$ 表示前 $i$ 支股票，预算为 $j$ 时的最大收益。那么答案就是 $f[n][budget]$。

对于第 $i$ 支股票，我们有两种选择：

  • 不购买，那么 $f[i][j] = f[i - 1][j]$；
  • 购买，那么 $f[i][j] = f[i - 1][j - present[i]] + future[i] - present[i]$。

最后返回 $f[n][budget]$ 即可。

时间复杂度 $O(n \times budget)$，空间复杂度 $O(n \times budget)$。其中 $n$ 为数组长度。

我们可以发现，对于每一行，我们只需要用到上一行的值，因此可以将空间复杂度优化到 $O(budget)$。

1
2
3
4
5
6
7
8
9
class Solution:
    def maximumProfit(self, present: List[int], future: List[int], budget: int) -> int:
        f = [[0] * (budget + 1) for _ in range(len(present) + 1)]
        for i, w in enumerate(present, 1):
            for j in range(budget + 1):
                f[i][j] = f[i - 1][j]
                if j >= w and future[i - 1] > w:
                    f[i][j] = max(f[i][j], f[i - 1][j - w] + future[i - 1] - w)
        return f[-1][-1]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    public int maximumProfit(int[] present, int[] future, int budget) {
        int n = present.length;
        int[][] f = new int[n + 1][budget + 1];
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= budget; ++j) {
                f[i][j] = f[i - 1][j];
                if (j >= present[i - 1]) {
                    f[i][j] = Math.max(
                        f[i][j], f[i - 1][j - present[i - 1]] + future[i - 1] - present[i - 1]);
                }
            }
        }
        return f[n][budget];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maximumProfit(vector<int>& present, vector<int>& future, int budget) {
        int n = present.size();
        int f[n + 1][budget + 1];
        memset(f, 0, sizeof f);
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= budget; ++j) {
                f[i][j] = f[i - 1][j];
                if (j >= present[i - 1]) {
                    f[i][j] = max(f[i][j], f[i - 1][j - present[i - 1]] + future[i - 1] - present[i - 1]);
                }
            }
        }
        return f[n][budget];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
func maximumProfit(present []int, future []int, budget int) int {
    n := len(present)
    f := make([][]int, n+1)
    for i := range f {
        f[i] = make([]int, budget+1)
    }
    for i := 1; i <= n; i++ {
        for j := 0; j <= budget; j++ {
            f[i][j] = f[i-1][j]
            if j >= present[i-1] {
                f[i][j] = max(f[i][j], f[i-1][j-present[i-1]]+future[i-1]-present[i-1])
            }
        }
    }
    return f[n][budget]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
function maximumProfit(present: number[], future: number[], budget: number): number {
    const f = new Array(budget + 1).fill(0);
    for (let i = 0; i < present.length; ++i) {
        const [a, b] = [present[i], future[i]];
        for (let j = budget; j >= a; --j) {
            f[j] = Math.max(f[j], f[j - a] + b - a);
        }
    }
    return f[budget];
}

方法二

1
2
3
4
5
6
7
class Solution:
    def maximumProfit(self, present: List[int], future: List[int], budget: int) -> int:
        f = [0] * (budget + 1)
        for a, b in zip(present, future):
            for j in range(budget, a - 1, -1):
                f[j] = max(f[j], f[j - a] + b - a)
        return f[-1]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    public int maximumProfit(int[] present, int[] future, int budget) {
        int n = present.length;
        int[] f = new int[budget + 1];
        for (int i = 0; i < n; ++i) {
            int a = present[i], b = future[i];
            for (int j = budget; j >= a; --j) {
                f[j] = Math.max(f[j], f[j - a] + b - a);
            }
        }
        return f[budget];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    int maximumProfit(vector<int>& present, vector<int>& future, int budget) {
        int n = present.size();
        int f[budget + 1];
        memset(f, 0, sizeof f);
        for (int i = 0; i < n; ++i) {
            int a = present[i], b = future[i];
            for (int j = budget; j >= a; --j) {
                f[j] = max(f[j], f[j - a] + b - a);
            }
        }
        return f[budget];
    }
};

1
2
3
4
5
6
7
8
9
func maximumProfit(present []int, future []int, budget int) int {
    f := make([]int, budget+1)
    for i, a := range present {
        for j := budget; j >= a; j-- {
            f[j] = max(f[j], f[j-a]+future[i]-a)
        }
    }
    return f[budget]
}

评论