Best non-adjacent deliveries

Scenario

A parcel-delivery app lists the orders on one street, in the order of their door numbers. Each order carries a tip. Orders at neighbouring doors share one parking spot, so one courier can take at most one of any two neighbouring orders.

Your team lead asks: "Which orders should one courier take to collect the largest total tip?"

Your task

Write best_tips(tips).

tips[i] is the tip of the order at door i. Doors are numbered from 0 in a row.
The courier may not take two orders whose positions are next to each other, such as i and i + 1.
Return the largest total tip the courier can collect. The courier may take no order at all, but tips are never negative.

Examples

Example 1 (traced)#

text2 lines

Input:  tips = [6, 2, 3, 9, 4]
Output: 15

Let best[i] be the largest total from the first i orders. For the next order there are two choices.

Skip it, and keep best[i - 1]. Take it, and add its tip to best[i - 2], because its neighbour is then not taken. So best[i] = max(best[i - 1], best[i - 2] + tips[i - 1]).

i	Order added	Skip: best[i - 1]	Take: best[i - 2] + tip	best[i]
0	none			0
1	tip 6	0	0 + 6 = 6	6
2	tip 2	6	0 + 2 = 2	6
3	tip 3	6	6 + 3 = 9	9
4	tip 9	9	6 + 9 = 15	15
5	tip 4	15	9 + 4 = 13	15

The answer is best[5] = 15: take the orders with tips 6 and 9, which are not neighbours.

Example 2#

text2 lines

Input:  tips = [5, 1, 1, 5]
Output: 10

The two 5s are three doors apart, so the courier takes both.

Example 3#

text2 lines

Input:  tips = [4, 5, 4]
Output: 8

The 5 sits between two 4s and blocks both. The two 4s together give 8, which beats 5.

Constraints

1 ≤ len(tips) ≤ 100,000
0 ≤ tips[i] ≤ 10,000

What does n ≤ 100000 tell you?

There can be 100,000 orders. Each order can be taken or skipped, and the number of valid choices grows by about 1.6 times with every extra order. Trying them all never finishes. A table with one entry per order costs 100,000 small steps.

Scenario

Your team lead asks: "Which orders should one courier take to collect the largest total tip?"

Your task

Write best_tips(tips).

tips[i] is the tip of the order at door i. Doors are numbered from 0 in a row.
The courier may not take two orders whose positions are next to each other, such as i and i + 1.
Return the largest total tip the courier can collect. The courier may take no order at all, but tips are never negative.

Examples

Example 1 (traced)#

text2 lines

Input:  tips = [6, 2, 3, 9, 4]
Output: 15

Let best[i] be the largest total from the first i orders. For the next order there are two choices.

Skip it, and keep best[i - 1]. Take it, and add its tip to best[i - 2], because its neighbour is then not taken. So best[i] = max(best[i - 1], best[i - 2] + tips[i - 1]).

i	Order added	Skip: best[i - 1]	Take: best[i - 2] + tip	best[i]
0	none			0
1	tip 6	0	0 + 6 = 6	6
2	tip 2	6	0 + 2 = 2	6
3	tip 3	6	6 + 3 = 9	9
4	tip 9	9	6 + 9 = 15	15
5	tip 4	15	9 + 4 = 13	15

The answer is best[5] = 15: take the orders with tips 6 and 9, which are not neighbours.

Example 2#

text2 lines

Input:  tips = [5, 1, 1, 5]
Output: 10

The two 5s are three doors apart, so the courier takes both.

Example 3#

text2 lines

Input:  tips = [4, 5, 4]
Output: 8

The 5 sits between two 4s and blocks both. The two 4s together give 8, which beats 5.

Constraints

1 ≤ len(tips) ≤ 100,000
0 ≤ tips[i] ≤ 10,000

What does n ≤ 100000 tell you?