O(1) space O(n) time and 0 ms C soln


  • 1
    1
    #define max(a,b) ((a) > (b) ? (a) : (b))
    int max_array(int *t1, int t1Len, int *t2, int t2Len) {
       int i, res=0;
       for(i=0;i<t1Len;i++)
            res = (res < t1[i]) ? t1[i] : res;
       for(i=0;i<t2Len;i++)
            res = (res < t2[i]) ? t2[i] : res;
       return res;
    }
    
    int rob(int *nums, int numsSize) {
      int tmp1[3] = {0,0,0}, tmp2[3]={0,0,0};
      int i, cIdx1=0, cIdx2=0, res=0;
      if(!nums) return 0;
      if(numsSize ==1) return nums[0];
    
      tmp1[cIdx1++]=nums[0]; tmp1[cIdx1++] = tmp2[cIdx2++] = nums[1]; tmp2[cIdx2++]=nums[2];
      for(i=2;i<numsSize;i++)  {
        if(i<(numsSize-1)) {
          tmp1[cIdx1] = max((nums[i]+tmp1[cIdx1]), (nums[i]+tmp1[(cIdx1+1)%3]));
          cIdx1 = (cIdx1+1)%3;
        }
        if(i>2) {
          tmp2[cIdx2] = max((nums[i] + tmp2[cIdx2]), (nums[i] + tmp2[(cIdx2+1) %3]));
          cIdx2 = (cIdx2+1) %3;
        }
      }
      res = max_array(tmp1, 3, tmp2, 3);
      return res;
    }
    

    Core of this solution is that we only need latest three profit values to find the final solution.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.