/ * *

152. Maximum subarray of product

The title

Given an array of integers, nums, find the contiguous subarray with the largest product (that subarray contains at least one number) and return the product of that subarray.

Example 1:

Input: [2,3,-2,4] output: 6 explanation: the subarray [2,3] has a maximum product of 6. Example 2:

Input: [- 2, 0, 1] output: 0 explanation: the result can’t to 2, because [2, 1] is not an array.

Source: LeetCode link: leetcode-cn.com/problems/ma… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

The test code

Print (maxProduct ([2, 3, 2, 4]))

notes

The idea of this problem is similar to that of 53. The maximum suborder and the maximum suborder are calculated in one loop

The difference is that this is a product, and there’s a negative number of elements in the array so in addition to recording the maximum, you’re also recording the minimum and you’re just updating the maximum and the minimum every time

The code address

Github.com/zmfflying/Z… * /

The problem solving code

import Foundation func maxProduct(_ nums: Var maxPro = nums[0] var maxPro = nums[0] var var maxPro = nums[0] var var maxPro = nums[0] var var maxPro = nums[0] var var maxPro = nums[0] var var maxPro = nums[0] var var maxPro = nums[0] var var maxPro = nums[0] var var maxPro = nums[0] var var maxPro = nums[0] var var maxPro = nums[0] var var maxPro = nums[0] var res = maxPro var minPro = maxPro for i in 1.. <nums.count {let num = nums[I] = nums[I maxPro = max(num, max(tempMax * num, minPro * num)) minPro = min(num, min(minPro * num, tempMax * num)) res = max(maxPro, res) } return res }Copy the code

/ * *

121. The best time to buy and sell stocks

The title

Given an array prices, its ith element prices[I] represents the price of a given stock on day I.

You can only buy the stock on one day and sell it on a different day in the future. Design an algorithm to calculate the maximum profit you can make.

Return the maximum profit you can make from the transaction. If you can’t make any profit, return 0.

Example 1:

Input: [7,1,5,3,6,4] output: 5 explanation: buy on day 2 (stock price = 1) and sell on day 5 (stock price = 6), maximum profit = 6-1 = 5. Note that the profit cannot be 7-1 = 6, because the selling price needs to be higher than the buying price; Also, you can’t sell stocks before you buy them. Example 2:

Input: prices = [7,6,4,3,1] output: 0 explanation: in this case, no transaction is completed, so the maximum profit is 0.

Tip:

1 <= prices.length <= 105

0 <= prices[i] <= 104

Source: LeetCode link: leetcode-cn.com/problems/be… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

The test code

Print (maxProfit1 (,1,5,3,6,4 [7]))

notes

The whole point of this problem is you can only buy once and you can only sell once so you have to buy at the minimum and sell at the maximum difference

Keep updating the minimum to find the maximum difference

The code address

Github.com/zmfflying/Z… * /

The problem solving code

Func maxProfit1(_ prices: [Int]) -> Int {var res: Int = 0 var minP = for I in 1.. < price. count {let price = prices[I] minP = min(minP, price) Price - minP)} return profit2 (_ prices: [Int]) -> Int {var res: Int = 0 var pre: Int = 0 for i in 1.. <prices. Count {// let diff = prices[I] -prices [i-1] // Let diff = prices[I] -prices [i-1] // Pre = Max (pre + diff, Func maxProfit3(_ prices: [Int]) -> Int {var res: = Max (res, pre)} Int = 0 for i in 0.. <prices.count { let buyPrice = prices[i] var j = i + 1 while j < prices.count { let sellPrice = prices[j] res = max(res,  sellPrice - buyPrice) j += 1 } } return res }Copy the code

/ * *

70. Climb the stairs

The title

Suppose you’re climbing stairs. It takes n steps to get to the top.

You can climb one or two steps at a time. How many different ways can you climb to the top?

Note: given n is a positive integer.

Example 1:

Input: 2 Output: 2 Explanation: There are two ways to climb to the top of the building. \

  1. Order 1 + order 1 \
  2. 2 order,

Example 2:

Input: 3 Output: 3 Explanation: There are three ways to climb to the top of the building. \

  1. Order 1 + order 1 + Order 1 \
  2. Order 1 + order 2 \
  3. 2 order plus 1 order

Source: LeetCode link: leetcode-cn.com/problems/cl… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

The test code

print(climbStairs(3))

notes

dp[1] = 1

dp[2] = 2

Then, when it comes to the last step of DP [3], there are two methods that have taken one step: DP [3-1] = DP [2] = two methods that have taken two steps: DP [3-2] = DP [1] = one

Similarly, DP [4] = DP [4-1] + DP [4-2] = DP [3] + DP [2]

So dp[I] = dp[i-1] + dp[i-2]

The code address

Github.com/zmfflying/Z… * /

The problem solving code

import Foundation func climbStairs(_ n: Int) -> Int { if n < 3 { return n } var dp = [Int].init(repeating: 0, count: n+1) dp[1] = 1 dp[2] = 2 for i in 3... N {/ / core formula dp [I] = dp] [I - 1 + dp/I - 2} return dp [n]}Copy the code