Stock Max Profit (Single or Multiple Transactions)

Problem Given a sequence of stock prices, solve one of two variants (the interviewer will specify): Variant A: Single transaction You may complete at most one buy and one sell (buy must happen before sell). Compute the maximum profit. Variant B: Multiple transactions You may complete as many transactions as you like, but you can hold at most one share at a time (must sell before buying again). Compute the maximum profit. Input (stdin) Line 1: integer n Line 2: n integers prices[i] Line 3: integer mode (1 for Variant A, 2 for Variant B) Output (stdout) One integer: the maximum profit Constraints 1 <= n <= 2*10^5 0 <= prices[i] <= 10^9 Target time O(n) and extra space O(1) Examples Example Input 6 7 1 5 3 6 4 1 Output 5