Cacher is the code snippet organizer for pro developers

// a better version
int max_sum_non_contigious_subsequence(int A[], int N) {
    if(N == 1) return A[0];
    if(N == 2) return max(A[0], A[1]);
    int *dp = new int[N];
    dp[0] = A[0];
    dp[1] = max(A[0], A[1]);
    
    for(int i=2; i<N; i++) {
        dp[i] = max(dp[i-1], dp[i-2]+A[i]);    
    }
    return dp[N-1];
}

int get_max_non_continuous_subsequence(int *A, int N) {
        int inclu = A[0], exclu = 0;
        for(int i=1; i<N; i++) {
                int new_exclu = max(exclu, inclu);
                int new_inclu = exclu + A[i];
                inclu = new_inclu;
                exclu = new_exclu;
        }
        int re = max(inclu, exclu);
        return re >= 0 ? re : -1;
}

int main()
{
   int A[] = {1,2,3,-1,3,4,2,7,8,-2,9,4,4,5};
   cout << max_sum_non_contigious_subsequence(A, 14) << endl;
   cout << get_max_non_continuous_subsequence(A, 14) << endl;
}