# Array, Dynamic Programming

"""
Idea:
Since we just have one shot, what we need is find the best buy_in and sale_out day.
Once the profit less than zero which means loss , we need reassign buy_in.
As long as the profiy large than zero whichs mean prices[buy_in] < prices[sale_out], 
we needn't change the value of buy_in.
"""

class Solution:
    #time complexity: O(n), Space complexity:O(1)111
    def maxProfit(self, prices):
        buy_day = 0
        sale_day = buy_day+1
        profit = 0
        while(sale_day < len(prices)):
            tmp_profit = prices[sale_day]-prices[buy_day]
            if tmp_profit < 0:
                buy_day = sale_day
            elif tmp_profit>profit:
                profit = tmp_profit
            sale_day += 1
        return profit

import unittest
class UnitTest(unittest.TestCase):
    solution = Solution()
    def test_case_normal(self):
        prices = [7,1,5,3,6,4]
        self.assertEqual(self.solution.maxProfit(prices), 5)
    
    def test_with_same_element(self):
        prices = [7,6,5,4,3,2,1]
        self.assertEqual(self.solution.maxProfit(prices), 0)

unittest.main()
# Array, Dynamic Programming

"""
Idea:
Since we just have one shot, what we need is find the best buy_in and sale_out day.
Once the profit less than zero which means loss , we need reassign buy_in.
As long as the profiy large than zero whichs mean prices[buy_in] < prices[sale_out], 
we needn't change the value of buy_in.
"""

class Solution:
    #time complexity: O(n), Space complexity:O(1)111
    def maxProfit(self, prices):
        buy_day = 0
        sale_day = buy_day+1
        profit = 0
        while(sale_day < len(prices)):
            tmp_profit = prices[sale_day]-prices[buy_day]
            if tmp_profit < 0:
                buy_day = sale_day
            elif tmp_profit>profit:
                profit = tmp_profit
            sale_day += 1
        return profit

import unittest
class UnitTest(unittest.TestCase):
    solution = Solution()
    def test_case_normal(self):
        prices = [7,1,5,3,6,4]
        self.assertEqual(self.solution.maxProfit(prices), 5)
    
    def test_with_same_element(self):
        prices = [7,6,5,4,3,2,1]
        self.assertEqual(self.solution.maxProfit(prices), 0)

unittest.main()
# Array, Dynamic Programming Idea: Since we just have one shot, what we need is find the best buy_in and sale_out day. Once the profit less than zero which means loss , we need reassign buy_in. As long as the profiy large than zero whichs mean prices[buy_in] < prices[sale_out],  we needn't change the value of buy_in. #time complexity: O(n), Space complexity:O(1)111