Question

2291. Maximum Profit From Trading Stocks

中文文档

Description

You are given two 0-indexed integer arrays of the same length present and future where present[i] is the current price of the ith stock and future[i] is the price of the ith stock a year in the future. You may buy each stock at most once. You are also given an integer budget representing the amount of money you currently have.

Return _the maximum amount of profit you can make._

 

Example 1:

Input: present = [5,4,6,2,3], future = [8,5,4,3,5], budget = 10
Output: 6
Explanation: One possible way to maximize your profit is to:
Buy the 0th, 3rd, and 4th stocks for a total of 5 + 2 + 3 = 10.
Next year, sell all three stocks for a total of 8 + 3 + 5 = 16.
The profit you made is 16 - 10 = 6.
It can be shown that the maximum profit you can make is 6.

Example 2:

Input: present = [2,2,5], future = [3,4,10], budget = 6
Output: 5
Explanation: The only possible way to maximize your profit is to:
Buy the 2nd stock, and make a profit of 10 - 5 = 5.
It can be shown that the maximum profit you can make is 5.

Example 3:

Input: present = [3,3,12], future = [0,3,15], budget = 10
Output: 0
Explanation: One possible way to maximize your profit is to:
Buy the 1st stock, and make a profit of 3 - 3 = 0.
It can be shown that the maximum profit you can make is 0.

 

Constraints:

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

Solutions

Solution 1

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];
}

Solution 2

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]
}