Function leetcode_for_rust::cd0122_best_time_to_buy_and_sell_stock_ii::max_profit

pub fn max_profit(prices: Vec<i32>) -> i32

Solutions

Approach 1: Iteration

• Time complexity: O(0)

• Space complexity: O(1)

• Runtime: 0 ms

• Memory: 2.6 MB

impl Solution {
    pub fn max_profit(prices: Vec<i32>) -> i32 {
        if prices.len() <= 1 { return 0; }

        let mut sum = 0;
        for i in 0..prices.len() - 1 {
            if prices[i] < prices[i+1] { sum += prices[i+1] - prices[i]; }
        }
        sum
    }
}

Approach 2: Iteration

• Time complexity: O(0)

• Space complexity: O(1)

• Runtime: 0 ms

• Memory: 2.6 MB

use std::cmp::max;

impl Solution {
    pub fn max_profit(prices: Vec<i32>) -> i32 {
        if prices.len() <= 1 { return 0; }

        let mut max_profit = 0;
        for i in 1..prices.len() {
            max_profit += max(0, prices[i] - prices[i - 1]);
        }
        max_profit
    }
}

Approach 3: Dynamic Programming

• Time complexity: O(0)

• Space complexity: O(1)

• Runtime: 0 ms

• Memory: 2.6 MB

use std::cmp::max;

impl Solution {
    pub fn max_profit(prices: Vec<i32>) -> i32 {
        if prices.len() <= 1 { return 0; }

        let mut profits = vec![0; prices.len()];
        let mut max_profit = 0;
        let mut tmp_max = -prices[0];

        for i in 1..prices.len() {
            profits[i] = max(profits[i - 1], tmp_max + prices[i]);
            tmp_max = max(tmp_max, profits[i] - prices[i]);
            max_profit = max(max_profit, profits[i]);
        }

        max_profit
    }
}