# From intuitive to terse, three different well-commented solutions in C, all accepted as best-submission

• int rob0(int* nums, int size)
{
if(size == 0)
return 0;
if(size == 1)
return nums[0];
int *profits = (int*)malloc(sizeof(int)*size);
profits[0] = nums[0];
profits[1] = nums[1] > nums[0] ? nums[1] : nums[0];
for(int i = 2; i < size; i++)
{
int profit = profits[i-2] + nums[i];
if(profits[i-1] > profit)
profit = profits[i-1];
profits[i] = profit;
}
return profits[size-1];
}

//AC - 0ms;
int rob(int* nums, int size)
{
if(size == 0)
return 0;
if(size == 1)
return nums[0];
int profit0 = rob0(nums, size-1);
int profit1 = rob0(nums+1, size-1);
return profit0 > profit1? profit0 : profit1;
}

//AC - 0ms - using constant space;
int rob(int* nums, int size)
{
if(size == 0) return 0;
if(size == 1) return nums[0];
int pre0=0, cur0=0;
for(int i = 0; i < size-1; i++) //including the first;
{
int t = pre0; //t will be profits[i-2] here;
pre0 = cur0;
if(t+nums[i] > cur0) cur0 = t+nums[i];
}

int pre1=0, cur1=0;
for(int i = 1; i < size; i++) //excluding the first and including the last;
{
int t = pre1; //t will be profits[i-2] here;
pre1 = cur1;
if(t+nums[i] > cur1) cur1 = t+nums[i];
}
return cur0>cur1? cur0:cur1;
}

//AC - 0ms - actually there are only four different states we need to record;
int rob(int* nums, int size)
{
if(size == 1) return nums[0];
int inFirst=nums[0], exFirst=0; //including the first element, but include or exclude the current;
int inNoFirst=0, exNoFirst=0;//excluding the first, but include or exclude the current;
for(int i = 1; i < size; i++)
{
int preInFirst = inFirst; //handling the first included case;
inFirst = exFirst+nums[i];
exFirst = preInFirst > exFirst? preInFirst:exFirst;
int preInNoFirst = inNoFirst; //handle the first excluded case;
inNoFirst = exNoFirst+nums[i];
exNoFirst = preInNoFirst > exNoFirst? preInNoFirst:exNoFirst;
}
return inNoFirst > exFirst? inNoFirst:exFirst;
}

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