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.

Example:

Input:  arr[]={2,4,6,2,5}
Output: 13

Approach 1:

C++

#include <bits/stdc++.h>
using namespace std;

int findMaximumNonAdjacentSum(vector<int> &arr)
{
    int len = arr.size();
    if (len == 0)
    {
        return 0;
    }

    if (len == 1)
    {
        return arr[0];
    }

    int sum[len];
    sum[len - 1] = arr[len - 1];
    sum[len - 2] = max(arr[len - 1], arr[len - 2]);

    for (int i = len - 3; i >= 0; i--)
    {
        sum[i] = max(arr[i] + sum[i + 2], sum[i + 1]);
    }

    return sum[0];
}

int main()
{
    vector<int> arr = {2, 4, 6, 2, 5};

    cout << findMaximumNonAdjacentSum(arr);

    return 0;
}
//Time Complexity: O(n)
//Space Complexity: O(n)

Approach 2:

C++

#include <bits/stdc++.h>
using namespace std;

int findMaximumNonAdjacentSum(vector<int> &arr)
{
    int first = 0;
    int second = 0;

    for (int i = arr.size() - 1; i >= 0; i--)
    {
        int new_sum = max(arr[i] + second, first);
        second = first;
        first = new_sum;
    }

    return first;
}

int main()
{
    vector<int> arr = {2, 4, 6, 2, 5};

    cout << findMaximumNonAdjacentSum(arr);

    return 0;
}
//Time Complexity: O(n)
//Space Complexity: O(1)