Editorial

Let’s number the houses starting from the first index (the $i$-th house contains $a_i$ money). Let $f(i)$ be the maximum amount of loot after robbing houses from $1$ to the $i$-th.

Then $f(1)=a_1,f(2)=max(a_1,a_2)$.

When computing $f(i)$, consider two cases:

• If the $i$-th house is robbed, then the $(i-1)$-th house cannot be robbed. In this case, the profit will be $f(i-2)+a_i$.

  

• if the $i$-th house is not robbed, the profit will be $f(i-1)$.

  

Thus,

Let's store the values of $f(i)$ in the array $res$. The answer to the problem will be the value $f(n)=res[n]$.

Example

Let's consider the computation of $f(3)$. If we don't rob the $3$-rd house, the profit will be $f(2)=6$. If the $3$-rd house is robbed, we can rob the first house, gaining a profit of $f(1)=6$, plus the profit from robbing the $3$-rd house, which is $2$ (the total profit will be $6+2=8$).

Now, let's consider the computation of $f(4)$. If we don't rob the $4$-th house, the profit will be $f(3)=8$. If the $4$-th house is robbed, we can rob the first two houses, gaining a profit of $f(2)=6$, plus the profit from robbing the $4$-th house, which is $10$ (the total profit will be $6+10=16$).

Exercise

Compute the values of $f(i)$ for the following input data:

Algorithm realization

Declare the input array $a$ and the resulting array $res$.

#define MAX 1000001
long long a[MAX], res[MAX];

Read the input data.

scanf("%d",&n);
for(i = 1; i <= n; i++)
  scanf("%lld",&a[i]);

Compute the answer $re{s}_1$ for one house, and $re{s}_2$ for two houses.

res[1] = a[1];
if (n > 1) res[2] = max(a[1],a[2]);

Compute the answers for the remaining houses.

for(i = 3; i <= n; i++)
  res[i] = max(res[i - 2] + a[i], res[i - 1]);

Print the answer.

printf("%lld\n",res[n]);

Java realization

import java.util.*; 

class Main 
{
  static long a[] = new long[1000001];
  static long res[] = new long[1000001];

  public static void main(String[] args) 
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    for(int i = 1; i <= n; i++)
      a[i] = con.nextInt();
    
    res[1] = a[1];
    if (n > 1) res[2] = Math.max(a[1],a[2]);

    for(int i = 3; i <= n; i++)
      res[i] = Math.max(res[i - 2] + a[i], res[i - 1]);

    System.out.println(res[n]);
    con.close();
  }
}

Python realization

Read the input data.

n = int(input())
lst = list(map(int,input().split()))

Initialize the list $dp$.

dp = [0] * len(lst)

Compute the answer $d{p}_0$ for one house, and $d{p}_1$ for two houses.

dp[0] = lst[0]
if (n > 1): dp[1] = max(lst[0], lst[1])

Compute the answers for the remaining houses.

for i in range(2, len(lst)):
  dp[i] = max(dp[i-1], dp[i-2] + lst[i])

Print the answer.

print(dp[-1])