## Student Interview Question for fresherss

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.