121. Best Time to Buy and Sell Stock - Leetcode Python Solution

 121. Best Time to Buy and Sell Stock

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

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example 1:

Input: prices = [7,1,5,3,6,4]

Output: 5

Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.

Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

Input: prices = [7,6,4,3,1]

Output: 0

Explanation: In this case, no transactions are done and the max profit = 0.

Constraints:

1 <= prices.length <= 105

0 <= prices[i] <= 104

In [ ]:

from typing import List
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_profit = 0
        min_num = prices[0]
        for i in range (1,len(prices)):
          if prices[i]<min_num:
            min_num=prices[i]
          profit = prices[i] - min_num
          if max_profit<profit:
            max_profit=profit
        return max_profit

s = Solution()
s.maxProfit([7,6,4,3,1])

Out[ ]:

0

Boyer-Moore voting Algorithm

 The Boyer-Moore voting algorithm is an efficient algorithm used to find the majority element in a sequence of elements. The majority element is defined as the element that appears more than n/2 times in a sequence of n elements, where n is the length of the sequence.

The key idea behind the Boyer-Moore voting algorithm is to keep track of a potential majority element as you traverse the sequence, and to cancel out pairs of different elements. The algorithm iterates through the sequence and maintains two variables: a candidate for the majority element and a count representing the number of occurrences of the candidate.

Here's a step-by-step explanation of how the algorithm works:

Initialize two variables, candidate and count, to None and 0, respectively.

Iterate through the sequence one element at a time.

If count is 0, assign the current element to candidate.

If the current element is equal to the candidate, increment count by 1.

If the current element is different from the candidate, decrement count by 1.

After processing all elements in the sequence, the candidate variable should contain a potential majority element.

To verify whether the candidate is indeed the majority element, you can iterate through the sequence again, counting the occurrences of the candidate element. If the count of the candidate element is greater than n/2, it is the majority element.

The Boyer-Moore voting algorithm is efficient because it cancels out pairs of different elements, which means that even if there are multiple different elements in the sequence, the algorithm can still identify the majority element. It works in O(n) time complexity, where n is the length of the sequence, and requires only O(1) additional space