每日算法 953 表达式计算树求非连续元素的最大总和
目录
思路参考:stackoverflow
原题说明
Given a list of integers, write a function that returns the largest sum of non-adjacent numbers. Numbers can be 0
or negative.
For example, [2, 4, 6, 2, 5]
should return 13
, since we pick 2
, 6
, and 5
. [5, 1, 1, 5]
should return 10
, since we pick 5
and 5
.
Follow-up: Can you do this in O(N) time and constant space?
思路
这是一道典型的动态规划来解决的问题,假设A是给定的数组arr,另一个数组Sum表示从arr[0]…arr[i]中非连续元素的最大和。
|
|
代码
|
|