No. 44 – Dynamic Programming on Stolen Values

Problem: There are n houses built in a line, each of which contains some value in it. A thief is going to steal the maximal value in these houses, but he cannot steal in two adjacent houses because the owner of a stolen house will tell his two neighbors on the left and right side. What is the maximal stolen value?

For example, if there are four houses with values {6, 1, 2, 7}, the maximal stolen value is 13 when the first and fourth houses are stolen.

参考:http://codercareer.blogspot.com/2013/02/no-44-maximal-stolen-values.html

/* Copyleft: Ming Lin <minggr@gmail.com> */

#include <stdio.h>

int steal(int data[], int n)
{
	int stolen;
	int max;
	int i;

	max = data[0];
	stolen = 1;
	for (i = 1; i < n; i++) {
		if (stolen) {
			if (data[i] > data[i-1])
				max = max - data[i-1] + data[i];
			else
				stolen = 0;
		} else {
			max = max + data[i];
			stolen = 1;
		}
	}

	return max;
}

int main()
{
	int data[] = {6, 1, 2, 7, 3, 9, 4};
	int n = 7;

	printf("max steal: %d\n", steal(data, n));

	return 0;
}

 

Leave a Reply