[Algorithm] Largest sum of non-adjacent numbers
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 return13
, since we pick2
,6
, and5
.[5, 1, 1, 5]
should return10
, since we pick5
and5
.Follow-up: Can you do this in O(N) time and constant space
How to think?
Always start from make few assumption / examples to see the parttens:
For example:
[5,1,1,5]
Start from i = 0: max sum can be Math.max(5, 0)
// memo: [5]
Then i = 1: max sum can be Math.max(memo[0], arr[1]), which is memo[1] = Math.max(5, 1) ---> 5
// memo :: [5, 5]
Then i = 2: max sum can be Math.max(memo[i - 1], arr[i] + memo[i - 2]), which is memo[2] = Math.max(5, 1 +5) --> 6:
// memo :: [5, 5, 6]
Then i = 3, should follow i = 2 partten:
// memo :: [5, 5, 6, 10]
So now, we got our partten:
for i = 2 to length memo[i] = Math.max(memo[i - 1], memo[i - 2] + arr[i])
Code:
function maxNonAdjSum(arr) { const memo = new Array(arr.length).fill(0); memo[0] = Math.max(0, arr[0]); memo[1] = Math.max(arr[1], memo[0]); for (let i = 2; i < arr.length; i++) { memo[i] = Math.max(memo[i-1], arr[i] + memo[i - 2]); } return memo; } console.log(maxNonAdjSum([2, 4, 6, 2, 5])); // 13 console.log(maxNonAdjSum([5, 1, 1, 5])); // 10 console.log(maxNonAdjSum([2, 4, 6, 2, 5, -3, 4, 0])); // 17
To improve it furuther for space, we don't really need to keep 'memo' as a whole array, we just need to remember 3 values:
// [max_inc, max_not_inc, max]
And:
max = Math.max(max + max_inc, max_not_inc)
Cdoe:
function maxNonAdjSum2(arr) { let max_inc = Math.max(0, arr[0]); let max_not_inc = Math.max(arr[1], max_inc); let max = max_inc for (let i = 2; i < arr.length; i++) { max = Math.max(arr[i] + max_inc, max_not_inc); max_inc = max_not_inc; max_not_inc = max; } return max; } console.log(maxNonAdjSum2([2, 4, 6, 2, 5])); // 13 console.log(maxNonAdjSum2([5, 1, 1, 5])); // 10 console.log(maxNonAdjSum2([2, 4, 6, 2, 5, -3, 4, 0])); // 17
相关文章
- MCfamily挖矿采用独创POA (Proof-of-Account)机制
- ORA-00740: datafile size of (string) blocks exceeds maximum file size ORACLE 报错 故障修复 远程处理
- ORA-01118: cannot add any more database files: limit of string exceeded ORACLE 报错 故障修复 远程处理
- ORA-22976: incorrect number of arguments to MAKE_REF ORACLE 报错 故障修复 远程处理
- ORA-29962: fatal error occurred in the execution of ODCIINDEXALTER routine ORACLE 报错 故障修复 远程处理
- ORA-32483: duplicate name found in sort specification list for SEARCH clause of WITH clause ORACLE 报错 故障修复 远程处理
- ORA-41686: use of “collection” invalid for the primitive event ORACLE 报错 故障修复 远程处理
- ORA-44816: Number of Performance Classes is less than specified ORACLE 报错 故障修复 远程处理
- ORA-14131: enabled UNIQUE constraint exists on one of the tables ORACLE 报错 故障修复 远程处理
- 函数使用MySQL中SUM函数计算求和(mysql中的sum)
- keyRedis Java Adaptation: Managing Expiry of Keys(redisjava过期)
- Exploring the Power of Oracle Query Arrays: Tips and Techniques for Efficient Data Retrieval(oracle查询数组)
- MySQL SUM 条件下的计算结果分析(mysql sum 条件)
- 使用Oracle中的SUM字段获取总和的简单方法(oracle sum字段)
- MySQL中的SUM函数怎样运用(mysql中sum怎么用)
- MySQL中如何使用SUM函数(mysql中sum怎么用)
- MySQL中的Sum函数用法详解(mysql中sum使用)
- Oracle SUM累加数据求和分析之旅(oracle sum累加)
- Oracle SUM函数计算精度把它化整为零(oracle sum精度)
- Oracle SUM 慢得令人发指(oracle sum很慢)
- 集Oracle的Sum函数空集的期待(oracle sum为空)