Maximum Sum

View as PDF

Submit solution

All submissions

Best submissions

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 \leq 100 000$ .
$N$ $N$ lines, each with one positive integer in the sequence $\le 1\,000$ $\leq 1 000$ .

Output Specification

The maximum sum possible.

Comments

1

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

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

1

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.