Maximum Sum

View as PDF

Submit solution

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, 6, 10 is valid, while 5, 9, 10 is invalid since 9 and 10 are next to each other.
4, 6, 10 happens to be the optimal sum in this case, so 20 is the answer.

Input Specification

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

Output Specification

The maximum sum possible.


  • 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.