discontiguousMaxSum.cpp

/*
http://www.careercup.com/question?id=23594662
Given a sequence of numbers A(1) ..A(n), find the continuous subsequenceA(i)..A(j) for which the sum of elements is maximum. 
condition: we should not select two contiguous numbers

Solution:
Dp: F[i] = max(A[i], A[i] + F[i-2], F[i-1])
*/
#include <vector>
#include <iostream>
using namespace std;
int discontiguousMaxSum(vector<int> &vec) {
    int len = vec.size();
    if(len == 0) return 0;
    if (len == 1) return vec[0];
    vector<int> val(len, 0);
    val[0] = vec[0];
    val[1] = max(vec[0], vec[1]);
    for (int i = 2; i < len; i++) {
        val[i] = max(vec[i], vec[i] + val[i-2]);
        val[i] = max(val[i], val[i-1]);
    }
    return val[len-1];
}

int main() {
    int a[] = {1,3,5,-1,12,6,7,11};
    vector<int> vec(a, a + 8);
    
    int r = discontiguousMaxSum(vec);
    cout << r << endl;
    system("pause");
}