Maximum sum with no three consec

Description:

Given a sequence of positive numbers, find the maximum sum that can be formed which has
no three consecutive elements present.

Example:

Input: arr[] = {1, 2, 3}
Output: 5
We can't take three of them, so answer is
2 + 3 = 5
Input: arr[] = {3000, 2000, 1000, 3, 10}
Output: 5013
3000 + 2000 + 3 + 10 = 5013
Input: arr[] = {100, 1000, 100, 1000, 1}
Output: 2101
100 + 1000 + 1000 + 1 = 2101
Input: arr[] = {1, 1, 1, 1, 1}
Output: 4
Input: arr[] = {1, 2, 3, 4, 5, 6, 7, 8}
Output: 27

解题方法：

say we have two arrays: f and g;
f[i] represent the maximum sum if we select the element at position i
g[i] represent the maximnm sum if we donot select the element at position i
then f[i] = max(g[i - 2] + nums[i - 1] + nums[i], g[i - 1] + nums[i]);
g[i] = max(f[i - 1], g[i - 1]);

Time Complexity：

O(n)

完整代码：

int maxSum(vector<int>& nums) {
    int len = nums.size();
    if(len < 3) {
        int sum = 0;
        for(int i: nums)
            sum += i;
        return sum;
    }
    //init
    vector<int> f = {nums[0], nums[0] + nums[1]};
    vector<int> g = {0, nums[0]};
    //DP
    for(int i = 2; i < len; i++) {
        f[i] = max(g[i - 2] + nums[i - 1] + nums[i], g[i - 1] + nums[i]);
        g[i] = max(f[i - 1], g[i - 1]);
    }
    return g[len - 1] > f[len - 1] ? g[len - 1] : f[len - 1];
}