CareerCup

The simple solution is to use recursion here. The basic thought is the max sum is current element plus next element or current element plus one after next element.

In code :

jsbin.com/pixinad/edit?js,console

function maxSumHelper(data, index) {
  if (index >= data.length) {
    return 0; 
  }else {
    var n1 = data[index];
    return Math.max(
      n1 + maxSumHelper(data, index + 1), //sum with the current plus next
      n1 + maxSumHelper(data, index + 2) //sum with the current plus one after next
    );
  }
}

function maxSum(data) {
  return Math.max( 
    maxSumHelper(data, 0), //sum with the first element
    maxSumHelper(data, 1) //sum without the first element
  );
}

var data1 = [10, 20, 30, -10, -50, 40, -50, -1, -3];
console.log('maxSum: ' + maxSum(data1)); //outputs 89

var data2 = [-1, -2, -3, -4, -5];
console.log('maxSum: ' + maxSum(data2)); //outputs -6

The recursion is:

dp(i) = max[dp(i-2) + arrary[i], if i >= 0
                   dp(i-1) + array[i], if i >= 0
                   0] if i < 0

result = max(dp(len(array)-1), dp(len(array)-2)

can implement it using memoization or construct a dp array in an iterative
manner, and with constant space, optimizing further (because the recursion
only access last elements)

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int max_subsequence_sum_special(const vector<int>& arr) 
{
	vector<int> dp(arr.size() + 2, 0);
	for (size_t i = 0; i < arr.size(); ++i) {
		dp[i + 2] = max(dp[i] + arr[i], dp[i + 1] + arr[i]);
	}
	return max(dp[arr.size()+1], dp[arr.size()]);
}

int max_subsequence_sum_special_cs(const vector<int>& arr)
{
	int dpi = 0;
	int dpi1 = 0;
	for (size_t i = 0; i < arr.size(); ++i) {		
		int temp_dpi = dpi1;
		dpi1 = max(dpi1 + arr[i], dpi + arr[i]);
		dpi = temp_dpi;
	}
	return max(dpi1, dpi);
}

def findMaxSeq(ar):
    mxSum =0
    resAr =[]
    i=0
    while i < len(ar)-1:
        if ar[i] >0:
            resAr.append(ar[i])
            mxSum += ar[i]
        elif i > 0:
            if ar[i+1]>ar[i]:
                resAr.append(ar[i+1])
                mxSum += ar[i+1]
                i+=1
            else:
                resAr.append(ar[i])
                mxSum += ar[i]

        else:
            if ar[0] + ar[2] > ar[1]:
                resAr.append(ar[0])
                mxSum += ar[0]
            else:
                resAr.append(ar[1])
                mxSum += ar[1]
                i += 2
        i += 1

    return resAr,mxSum

if __name__== '__main__':
    ar = [-10,-2,-1,13,-5,20,-12]
    maxSeq, mxSum = findMaxSeq(ar)
    print (maxSeq, mxSum)

@ChrisK ..Can you tell me why it is like max(dp(len(array)-1), dp(len(array)-2) ?