| comments | difficulty | edit_url | tags | ||
|---|---|---|---|---|---|
true |
中等 |
|
给你两个下标从 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.length1 <= n <= 10000 <= present[i], future[i] <= 1000 <= budget <= 1000
我们定义
对于第
- 不购买，那么
$f[i][j] = f[i - 1][j]$ ； - 购买，那么
$f[i][j] = f[i - 1][j - present[i]] + future[i] - present[i]$ 。
最后返回
时间复杂度
我们可以发现，对于每一行，我们只需要用到上一行的值，因此可以将空间复杂度优化到
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]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];
}
}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];
}
};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]
}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];
}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]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];
}
}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];
}
};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]
}