Algorithm

To prevent auxiliary stack space used by recursion in memoization, and to optimize space and runtime, we use the tabulation (bottom-up DP) approach.

Create a DP array to store the maximum sum at each index.
Initialize the first value in the DP array as the first element of the input array because if there's only one element, that’s the only sum we can take.
For the second element, take the maximum between the first and the second element.
From the third element onward, for each index, calculate two options:

If we pick the current element, we add its value to the value at index two positions back in the DP array
If we don’t pick, just take the value from the previous index.

Take the maximum of the two options and store it in the current position in the DP array.
After processing all elements, the last value in the DP array will contain the maximum sum possible without picking adjacent elements.

Code

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

class Solution {
public:
    // Function to return maximum sum of non-adjacent elements
    int maximumNonAdjacentSum(vector<int>& arr) {
        // Get the size of array
        int n = arr.size();

        // If array has only one element, return it
        if (n == 1) return arr[0];

        // Initialize dp array of size n
        vector<int> dp(n);

        // Base case: only one element
        dp[0] = arr[0];

        // Base case: max of first or second element
        dp