[Algorithm] Leecode_Best Time to Buy and Sell Stock II

Problem

Question
You are given an integer array prices where prices[i] is the price of a given stock on the ith day.

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.
Example 2:

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Total profit is 4.
Example 3:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.

Constraints:

• 1 <= prices.length <= 3 * 104
• 0 <= prices[i] <= 104

Analysis & Solution

• 모든 배열을 순회하면서,
  다음 값이 더 크면 값을 더해 주고, 현재값 마이너스
• Dynamic Programming 참고

  Daynamic Programming
  동적 프로그래밍은 수학적 최적화 방법
  하나의 문제를 한번만 풀도록 하기 때문에 효율적
  분할 정복과는 다름
  풀이방법은 Memoization / Bottom-up, Top-down 방식이 있음

Code (C++)

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int sum = 0;
        for(int i=0;i<prices.size()-1;i++)
        {
            if(prices[i+1]>prices[i])
                sum = sum + prices[i+1]-prices[i];
        }
        return sum;
    }
};

Reference
[1] https://medium.com/theleanprogrammer/best-time-to-buy-and-sell-stock-ii-140d90750ebd