Leetcode: House Robber II

House Robber II

My Submissions

Total Accepted: 17938 Total Submissions: 62688 Difficulty: Medium

Note: This is an extension of House Robber.

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.

Subscribe to see which companies asked this question

Hide Tags

 Dynamic Programming

Show Similar Problems

```````````````````````````````````````````````````````````````````````````````````````````

DP:

Based on House Robber, we divide the input into two kinds:

e.g., nums= 1 2 3 5 4 3 2, we divide it into sub inputs:

            n1=  1 2 3 5 4 3 

            n2=     2 3 5 4 3 2, 

and then use the House Robber to run the two respectively and in then end choose the maximal one from the two results. 

/////////////////////////////////////////////////////////////////////////////

//codes

 class Solution {

 public:

int robSub(vector<int>& nums, int left, int right){

if (right - left == 0)return nums[left];

vector<int> dp;

int len = nums.size(), used = 0;

dp.assign(len, 0);

dp[left] = nums[left];

dp[left + 1] = max(nums[left + 1], nums[left]);

for (int i = left + 2; i <= right; i++){

if (nums[i] + dp[i - 2]>dp[i - 1]){

dp[i] = nums[i] + dp[i - 2];

}

else dp[i] = dp[i - 1];

}

return max(dp[right - 1], dp[right]);

}

int rob(vector<int>& nums) {

//check input

if (nums.empty())return 0;

if (nums.size() == 1)return nums[0];

int size = nums.size();

return max(robSub(nums, 0, size - 2), robSub(nums, 1, size - 1));

}

 };

Leetcode: House Robber

House Robber

My Submissions

Total Accepted: 44878 Total Submissions: 140360 Difficulty: Easy

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Credits:
Special thanks to @ifanchu for adding this problem and creating all test cases. Also thanks to @ts for adding additional test cases.

Subscribe to see which companies asked this question

Hide Tags

 Dynamic Programming

Show Similar Problems

```````````````````````````````````````````````````````````````````````````

DP: updating rules:

dp[0] = num[0] 
dp[1] = max(num[0], num[1]) 
dp[i] = max(num[i] + dp[i - 2], dp[i - 1]) 

//////////////////////////////////////////////////////////////

//CODE

    class Solution {

    public:

        int rob(vector<int> &num) {

            if(num.empty()){

                return 0;

            }//if

            int size = num.size();

            if(size==1){

                return num[0];

            }

            

            vector<int> dp(size,0);

            dp[0] = num[0];

            dp[1] = max(num[0],num[1]);

            for(int i = 2;i < size;++i){

                dp[i] = max(dp[i-1],dp[i-2]+num[i]);

            }//for

            return dp[size-1];

        }

    };

Leetcode: Maximum Product Subarray

Maximum Product Subarray

My Submissions

Total Accepted: 46701 Total Submissions: 224496 Difficulty: Medium

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

Subscribe to see which companies asked this question

Hide Tags

 Array Dynamic Programming

Show Similar Problems

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

DP:

Using max, min to store the previous maximal and minimal produce, and a gmax to keep the biggest one. 

To calculate the max and min, we will encounter several cases:

for nums[i] we have: CASE A; CASE B; CASE C;

FOR max and min, we have:

case 1~case4;

see figure below:

/////////////////////////////////////////////////////////////////

//codes

class Solution {

 public:

        int maxProduct(vector<int>& nums) {

               //check input

               if (nums.size() == 1)return nums[0];

               int ma = nums[0], mi = nums[0], gMax = nums[0];

               for (int i = 1; i<nums.size(); i++){

                      if (nums[i]>0){ //case A  

                            if (ma<0){ mi = nums[i] * mi; ma = nums[i]; } //case 1

                            else if (mi>0) { mi = nums[i]; ma = ma*nums[i]; }//case 2

                            else if (mi == 0 || ma == 0) { mi = nums[i]; ma = nums[i]; }//case 3

                            else { mi = nums[i] * mi; ma = nums[i] * ma; }//case 4

                      }

                      else if (nums[i]<0){ //CASE B

                            if (ma<0){ ma = nums[i] * mi; mi = nums[i]; }

                            else if (mi>0) { mi = nums[i] * ma; ma = nums[i]; }

                            else if (mi == 0 || ma == 0) { mi = nums[i]; ma = nums[i]; }

                            else { int tmp = mi; mi = nums[i] * ma; ma = nums[i] * tmp; }

                      }

                      else{ // is 0  //CASE C

                            mi = 0; ma = 0;

                      }

                      gMax = gMax<ma ? ma : gMax;

               }

               return gMax;

        }

 };

Leetcode: Best Time to Buy and Sell Stock (8ms)

Best Time to Buy and Sell Stock

My Submissions

Total Accepted: 76857 Total Submissions: 223909 Difficulty: Medium

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

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Subscribe to see which companies asked this question

Hide Tags

 Array Dynamic Programming

Show Similar Problems

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Using several variables to store the values:

'low'  to store the current lowest point;

'profit' to store the current highest profit;

'slop' to store the up slop and down slop: in order to find the peaks and valleys. 

Note: don't need to store the high points. 

NOTE: some corner cases:

1. the end point in up slop

2.   [1,9 ,0 ,9] -- in such case, when in last 9, slop is still not updated yet. 

/////////////////////////////////////////////////////////////////////////////////

//codes

class Solution {

 public:

        int maxProfit(vector<int>& prices) {

               //input check

               if (prices.size()<2)return 0;

               int low, high, profit, slop;

               if (prices[1]>prices[0]){

                      low = prices[0]; high = prices[1]; slop = 1; profit = prices[1] - prices[0];

               }

               else{

                      low = prices[1]; high = prices[0]; slop = -1; profit = 0;

               }

               for (int i = 2; i<prices.size(); i++){

                      if (i == prices.size() - 1 && prices[i]>prices[i - 1])//slop==1)//last value

                      {

                            low = prices[i - 1]<low ? prices[i - 1] : low;

                            profit = prices[i] - low>profit ? prices[i] - low : profit;

                      }

                      else if (slop == -1 && prices[i]>prices[i - 1])//low point

                      {

                            low = prices[i - 1]<low ? prices[i - 1] : low;

                            slop = 1;

                      }

                      else if (slop == 1 && prices[i]<prices[i - 1])//high point

                      {

                            profit = prices[i - 1] - low>profit ? prices[i - 1] - low : profit;

                            slop = -1;

                      }

                      else continue;

               }

               return profit;

        }

 };

/////////another two methods
/*
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size()==0)return 0;
        //using two loops
        //outter loop swip from i->end
        //inner loop swip from i+1->end
        int profit=0, min=prices[0]+1;
        for(int i=0;i<prices.size();i++){
            if(prices[i]>=min)continue;//skip some unessisary cases
            else min=prices[i];
            for(int j=i+1;j<prices.size();j++){
                if(prices[j]-prices[i]>profit)profit=prices[j]-prices[i];
            }
        }
        return profit;
    }
};
*/


///the third method 
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size()<2)return 0;
        //using two parameters to store the value: profit, min
        int profit=prices[1]-prices[0]>0?prices[1]-prices[0]:0, min=prices[0];
        for(int i=1;i<prices.size();i++){
            if(prices[i]<min)min=prices[i];
            else if (prices[i]-min>profit)profit=prices[i]-min;
        }
        return profit;
    }

};