[알고리즘문제] 릿코드 Best Time to Buy and Sell Stock(시간초과, brute force)

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

Best Time to Buy and Sell Stock - LeetCode

주식을 매수/매도 하여 가장 큰 차익의 결과를 반환하는 문제이다. 수익을 낼 수 없다면 0을 반환해야 된다.

숫자 배열이 주어진다.

index는 하루를 의미하고 각 숫자는 그날의 주식 가격을 의미한다.

ex) [7, 1, 5, 4, 6, 4]배열이 주어지면 배열의 가장 큰 차익을 발생시키는 결과는 1 과 6의 차이인 5이다.

ex) [7, 6, 4, 3, 1]배열이 주어지면 수익을 낼 수 없는 구조이므로 0을 반환한다.

impl Solution {
    pub fn max_profit(prices: Vec<i32>) -> i32 {
        let mut compare = 0;
        for i in 0..prices.len(){
            for j in i..prices.len(){
                if prices[i] < prices[j] && compare < (prices[j] - prices[i]){
                    compare = prices[j] - prices[i];
                }
            }
        }
        compare
    }
}

위의 코드와 같이 brute force로 풀게 된다면 시간 초과가 발생한다.