###### tags: `Week_1`, `Greedy`

# Greedy

## [121. Best Time to Buy and Sell Stock](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/)

harry

# @param {Integer[]} prices
# @return {Integer}
def max_profit(prices)
  # profit at nth day = price[N] - 看前面幾天可以買到的最便宜價格
  # profit = 
  #  { n > 1, m: max(price[n] - min_cost_til_now, 0))
  #  { n == 1: -1
  profit = 0
  min_cost_til_now = 10001
  prices.each_with_index do |price, i|
    if price < min_cost_til_now
      min_cost_til_now = price
    elsif price - min_cost_til_now > profit
      profit = price - min_cost_til_now
    end
  end
  profit
end

beny

public class Solution {
    public int MaxProfit(int[] prices) {
        int maxProfit = 0;
        int minbuy = prices[0];    
        for(int i = 0; i < prices.Length; i++){                    
            if(minbuy > prices[i]){
                minbuy = prices[i];
            }
            if(prices[i] - minbuy > maxProfit){
                maxProfit = prices[i] - minbuy;
            }            
        }
        return maxProfit;
    }
}

Sam:

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        
        max_profit = 0
        min_price = 10000000
        
        for i in range(len(prices)):
            if (prices[i] < min_price):
                min_price = prices[i]
            elif (prices[i] - min_price) > max_profit:
                max_profit = prices[i] - min_price
                
        return max_profit

## [409. Longest Palindrome](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/)
harry

# @param {String} s
# @return {Integer}
def longest_palindrome(s)
  occurences = s.chars.tally.values
  count = 0
  return occurences.first if occurences.size == 1

  sum = 0
  occurences.each do |occur|
    count += if occur.even?
               occur
             else
               occur - 1
             end
    sum += occur
  end

  count += 1 if sum > count
  count
end

#NOTE: tally 
s = "abbccc"
s.chars.tally
# {
#   a: 1, b:2, c:3
# }

beny

public class Solution {
    public int LongestPalindrome(string s) {
        Dictionary<char,int> even = new Dictionary<char,int>();
        int result = 0;
        for(int i = 0; i < s.Length; i++){            
            if(!even.ContainsKey(s[i])){
                 even.Add(s[i],1);
            }else{
                if(even[s[i]] % 2 == 1){
                    result = result + 2;
                    even[s[i]] = 2;
                }else{
                    even[s[i]] = 1;                    
                }        
            }           
        }        
        if(even.ContainsValue(1)){
            result += 1;
        }
        return result;
    }
}

Hazel:

function longestPalindrome(s) {
  let mapping = {};
  let result = 0;
  for (let i = 0; i < s.length; i++) {
    if (!mapping[s[i]]) {
      mapping[s[i]] = 1;
    } else {
      result += 2;
      mapping[s[i]] = 0;
    }
  }
  if (Object.values(mapping).some((e) => e === 1)) {
    return (result += 1);
  }
  return result;
}

Sam:

class Solution:
    def longestPalindrome(self, s: str) -> int:
        
        count_map = dict()
        
        for c in s:
            if c not in count_map:
                count_map[c] = 1
            else:
                count_map[c] += 1
        
        pair_count = 0
        has_middle_word = False
        for k,v in count_map.items():
            pair_count += v // 2
            if v % 2 ==1:
                has_middle_word = True
                
        return pair_count * 2 + 1 if has_middle_word else pair_count * 2