Maximum Sum

Points: 7

Time limit: 1.0s

Memory limit: 16M

Problem type

Given an array of (positive) integers, find a subset with the maximal sum.
However, there is the additional restriction that no two numbers in the subset may be adjacent.

For example, for the array $4, 5, 6, 9, 10$ ~4, 5, 6, 9, 10~:
$4, 6, 10$ ~4, 6, 10~ is valid, while $5, 9, 10$ ~5, 9, 10~ is invalid since $9$ ~9~ and $10$ ~10~ are next to each other.
$4, 6, 10$ ~4, 6, 10~ happens to be the optimal sum in this case, so $20$ ~20~ is the answer.

Input Specification

An integer $1 < N \le 100\,000$ ~1 < N \le 100\,000~.
$N$ ~N~ lines, each with one positive integer in the sequence $\le 1\,000$ ~\le 1\,000~.

Output Specification

The maximum sum possible.

Comments

0

thunder200911133 commented on April 19, 2024, 6:01 p.m.

If anyone is stuck, it's the same logic as the leetcode 198

0

Vastaway commented on Jan. 26, 2024, 4:23 a.m.

For anyone getting an MLE on the last test case with CPython3 (with just a tiny bit more memory exceeded), try using arrays instead of lists! You can still solve this question with just Python lists, but if you have slightly sub-optimal code (in terms of memory), it's an option to consider.

Of course, another way is to try and accomplish the same task with less lists/arrays, etc.