Student Interview Question
fresherssCountry: 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