Simple Java 5 line solution, O(n) time, O(1) space

  • 7
    if(num.length==0) return 0;
    if(num.length==1) return num[0];
    num[1] = Math.max(num[0], num[1]);
    for(int i=2;i<num.length;i++) num[i] = Math.max(num[i]+num[i-2], num[i-1]);
    return num[num.length-1];

  • 0

    This solution is good. But the content of num[i] is overwrite.
    Could use 3 variable to hold num[i-2], num[i-1] and num[i].

  • 0

    Sure, that's a good point!
    But I didn't want to use extra space. If you don't want to lose the original array you can certainly use some extra variable to hold the computed values, as you said :)

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.