O(1) Space efficient solution

max_non_adjacent_sum.cpp

//Function to return the maximum sum without adding adjacent elements.
// include/ exclude DP
long long maximumSum(int arr[], int sizeOfArray) {
    //Your code here
    // edge case: if all the elements are negative
    bool flag = true;
    int max_val = INT_MIN;
    for(int i = 0; i < sizeOfArray; i++) {
        if(arr[i] > 0) {
            flag = false;
            break;
        }
        if(arr[i] > max_val)
            max_val = arr[i];
    }
    // all negative values are there
    if(flag)
        return max_val;
    
    long long prev_incl = arr[0], prev_excl = 0;
    long long cur_incl, cur_excl;
    for(int i = 1; i < sizeOfArray; i++) {
        cur_incl = prev_excl + arr[i];
        cur_excl = max(prev_incl, prev_excl);
        // update values for next iteration
        prev_incl = cur_incl;
        prev_excl = cur_excl;
    }
    return max(cur_incl, cur_excl);
}