Pybites Logo

Art thief

Level: Advanced (score: 4)

You are a professional art thief with a penchant for post-war American painting, sun-soaked French islands, and money. You have been on vacation for the past 3 weeks.

Due to ongoing wildfires pretty much everywhere, your flight home from St. Barths to Paris has been re-routed through New York City, gifting you a layover and time to kill.

You remember an article from your "Horizons" in-flight magazine describing a current MoMa exhibit of Abstract Expressionist paintings. You decide to hit it.

Your plan is to:

- Focus on one gallery only

- Maximize your haul (haul = "proceeds from a theft")

- Avoid getting caught.

Oh and one more thing:

    - all the paintings in the gallery are part of a networked security system

    - If you steal two adjacent paintings, you will trigger the alarm, which will alert the cops, who will arrest you.

TL;DR

- You are a thief trying to steal paintings, and you have n paintings in front of you.

- You can steal paintings, but you cannot steal two consecutive paintings because that will trigger an alarm.

- Each painting has a value represented by an integer.

- You want to find the maximum value you can obtain by stealing paintings without ever taking two consecutive ones.

Examples:

1.

>>> from art_thief import art_thief
>>> paintings = [2, 7, 9, 3, 1]
>>> art_thief(paintings)
12
# Explanation:
# Steal the first painting (value = 2)
# Steal the third painting (value = 9)
# Steal the fifth painting (value = 1)
# 2 + 9 + 1 = 12 

2.

>>> from art_thief import art_thief
>>> paintings = [3, 1, 10, 50, 2, 9]
>>> art_thief(paintings)
62
# Explanation:
# Steal the first painting (value = 3)
# Steal the fourth painting (value = 50)
# Steal the sixth painting (value = 9)
# 3 + 50 + 9 = 62

3.

>>> from art_thief import art_thief
>>> paintings = [6, 1, 9, 7, 4, 8, 3, 5, 2, 10]
>>> art_thief(paintings)
38
# Explanation:
# Steal the first painting (value = 6)
# Steal the third painting (value = 9)
# Steal the sixth painting (value = 8)
# Steal the eigth painting (value = 5)
# Steal the tenth painting (value = 10)

Hint:

Your solution needs to consider the possibility of stealing non-consecutive paintings that aren't strictly in an even-odd pattern (see Examples 2 and 3).

Keep calm and code in Python!