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!