## Student Interview Question

fresherss**Country:**United States

**Interview Type:**Phone Interview

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)
```

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 :

- tnutty2k8 August 25, 2017