# Daily Coding Challenge #80

This is a series of Daily Coding Challenge. Each day I show a few solutions written in C++. The questions are from coding practice/contest sites such as HackerRank, LeetCode, Codeforces, Atcoder and etc.

/*
LeetCode - Best Time to Buy and Sell Stock with Cooldown

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)
Example:

Input: [1,2,3,0,2]
Output: 3
*/

class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
if(n<2) return 0;
// profit at index i for 3 states - rest, buy & sell
vector<int> s0(n,0), s1(n,0), s2(n,0);
// s0 -> s1 -> s2 -> s0 ..
// s0 - rest -> (s0/s1)
// s1 - buy  -> (s1/s2)
// s2 - sell -> (s0)
s0[0]=0;
s1[0]=-prices[0];
s2[0]=INT_MIN;
for(int i=1;i<n;i++){
s0[i]=max(s0[i-1],s2[i-1]);
s1[i]=max(s1[i-1],s0[i-1]-prices[i]);
s2[i]=s1[i-1]+prices[i];
}
return max(s0[n-1],s2[n-1]);
}
};

class Solution2 {
public:
int maxProfit(vector<int>& prices) {
// simplified Solution1
int n = prices.size();
if(n<2) return 0;
// profit at index i for 3 states - rest, buy & sell
// s0 -> s1 -> s2 -> s0 ..
// s0 - rest -> (s0/s1)
// s1 - buy  -> (s1/s2)
// s2 - sell -> (s0)
for(int i=1;i<n;i++){
int prev_sell=sell;
rest=max(rest, prev_sell);
}
return max(rest,sell);
}
};

/*
LeetCode - Detect Capital

Given a word, you need to judge whether the usage of capitals in it is right or not.

We define the usage of capitals in a word to be right when one of the following cases holds:

All letters in this word are capitals, like "USA".
All letters in this word are not capitals, like "leetcode".
Only the first letter in this word is capital, like "Google".
Otherwise, we define that this word doesn't use capitals in a right way.

Example 1:

Input: "USA"
Output: True

Example 2:

Input: "FlaG"
Output: False

Note: The input will be a non-empty word consisting of uppercase and lowercase latin letters.
*/

class Solution {
public:
bool detectCapitalUse(string word) {
int c1=0,c2=0,n=word.size();
for(char c:word){
if(c>='A'&&c<='Z') c1++;
else c2++;
}
return (
c1==n ||
c2==n ||
word[0]>='A'&&word[0]<='Z' && c2==n-1
);
}
};


The source code is available in corresponding repo below. Star and watch for timely updates!

## wingkwong / atcoder

Posted on by:

### Wing-Kam

Consultant by day. Developer by night. AWS certified. Exploring #CloudNative currently.