## Yahoo Facebook Interview Question for Software Engineer / Developers

• 2

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
7
of 9 vote

Clear case of Dynamic Programming.

Follows the recursive structure:
currentSum = max{A[i], max{A[i-2] + A[i], A[i-2]}, max{A[i-3] + A[i], A[i-3]}, } // i runs from 2 to N.

Full working implementation in java is given below. Give the input numbers using space as delimiter.
Eg: 1 - 1 3 8 4
1 5 3 9 4
1 2 3 4 5

``````import java.util.ArrayList;
import java.util.Scanner;
import java.util.regex.Pattern;

public class MaxSumSubset {

static ArrayList<Integer> input = new ArrayList<Integer>();

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
Pattern pattern = Pattern.compile(System.getProperty("line.separator")
+ "|\\s");
scanner.useDelimiter(pattern);

int intval, tempMax = 0;

while (scanner.hasNextInt()) {
intval = scanner.nextInt();
}

int[] vals = new int[input.size()];

if (vals.length > 1) {
vals[0] = input.get(0);
vals[1] = Math.max(input.get(0), input.get(1));

for (int i = 2; i < input.size(); i++) {

tempMax = Math.max(vals[i - 2], vals[i - 2] + input.get(i));

vals[i] = Math.max(tempMax, input.get(i));
if (i - 3 >= 0) {

int tempMax2 = Math.max(vals[i - 3],
vals[i - 3] + input.get(i));
vals[i] = Math.max(tempMax2, vals[i]);
}
}
}
tempMax = -99999999;
for (int i = 0; i < vals.length; i++) {
if (vals[i] > tempMax) {
tempMax = vals[i];
}
}
System.out.println("Maximum sum=" + tempMax);
}
}``````

Edited to fix the bug as suggested by Celgin

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

@Dumbo: Nice logic
Code in C:

``````int max(int a, int b, int c)
{
int temp = a>b?a:b;
return temp>c?temp:c;
}

int main()
{
int maxi=0,i;
int a[] = {1, 5, 3, 9, 4};

for(i=2;i<sizeof(a)/sizeof(a[0]);i++){
a[i] = max(a[i], a[i-1], a[i]+a[i-2]);
}
printf("%d\n", a[(sizeof(a)/sizeof(a[0]))-1]);
}``````

Comment hidden because of low score. Click to expand.
2

slight bug in earlier version.So new code:

``````int max3(int a, int b, int c, int d)
{
int temp = a>b?a:b;
int temp1 = c>d?c:d;
return temp>temp1?temp:temp1;
}

int main()
{
int maxi=0,i;
int a[] = {1,3,5,-1,12,6,7,11};

for(i=2;i<sizeof(a)/sizeof(a[0]);i++){
a[i] = max3(a[i-2], a[i-1], a[i]+a[i-2], a[i]);
//printf("%d\n", a[i]);
}
printf("%d\n", a[(sizeof(a)/sizeof(a[0]))-1]);
}``````

Comment hidden because of low score. Click to expand.
5

Sorry, but there is a bug i thik.
Consider array = [1,3,5,-1,12,6,7,11]
Your code result is 25 with (1+5+12+7); however it should be 29 (1+5+12+11)

import java.util.ArrayList;
import java.util.Scanner;
import java.util.regex.Pattern;

public class MaxSumSubset {

static ArrayList<Integer> input = new ArrayList<Integer>();

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
Pattern pattern = Pattern.compile(System.getProperty("line.separator")
+ "|\\s");
scanner.useDelimiter(pattern);

int intval, tempMax = 0;

while (scanner.hasNextInt()) {
intval = scanner.nextInt();
}

int[] vals = new int[input.size()];

if (vals.length > 1) {
vals[0] = input.get(0);
vals[1] = Math.max(input.get(0), input.get(1));

for (int i = 2; i < input.size(); i++) {
tempMax = Math.max(vals[i - 2], vals[i - 2] + input.get(i));
vals[i] = Math.max(tempMax, input.get(i));
if (i - 3 >= 0) {

int tempMax2 = Math.max(vals[i - 3], vals[i - 3] + input.get(i));
vals[i] = Math.max(tempMax2, vals[i]);
}
}
}
tempMax = -99999999;
for (int i = 0; i < vals.length; i++) {
if (vals[i] > tempMax) {
tempMax = vals[i];
}
}
System.out.println("Maximum sum=" + tempMax);
}
}

following update will solve the problem

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

@cengin: Thanks modified now and it works for all the cases.

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

@cengin, aka

Thanks for the bug fix. Yeah, it is working fine now.

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

The function name should be max4, instead of max3 then ;-)

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

It fails for the input [1,0,4,-3,2] - return "7".

Comment hidden because of low score. Click to expand.
2
of 4 vote

You can do this in linear time using dynamic programming. Here's the function you would want to call, giving it the array of numbers and the length of the array:

``````int maxsubsetsum(int lst[], int numItems) {
if (numItems == 0) {
return 0; // something to signify an empty array was passed in
} else if (numItems == 1) {
return lst[0];
}

int S[numItems];
S[0] = lst[0];
S[1] = getMax(lst[0], lst[1]);

int i = 0;
for (i = 2; i < numItems; i++) {
S[i] = getMax(lst[i] + S[i-2], S[i-1]);
}
return S[numItems-1];
}``````

Comment hidden because of low score. Click to expand.
-2

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

I don't think he does, because he uses either the current number plus the max from 2 turns ago, or the max from 1 turn ago without the current number.

``getMax(lst[i] + S[i-2], S[i-1]);``

So he's not using adjacent numbers.

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

Code is clean and concise, but I think it only works for lists of positive numbers. Counterexample: [8, 7, -2, -2]

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

Kadence solution should work I guess but only difference would be here we have to consider only adjacent numbers.

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

not handled all cases. Please try with {-3, -2, 1}

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

I think if you just add

``````if(S[0] < 0)
S[0] = 0;
if(S[1] < 0)
S[1] = 0;``````

it'll work properly. It already handles negative cases (since adding will make it smaller than the max), just not if they're in one of the first two items.

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

@Vin

I think the bug lies in

``S[i] = getMax(lst[i] + S[i-2], S[i-1]);``

should not consider S[i-1] as it is an adjacent element

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

@Dumbo
he is considering S[i-1] by itself, or S[i-2] + the current value. So he's not adding the current value to the last value.

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

``````#include <iostream>
#include <string>
#include <sstream>
#include <set>
#include <conio.h>
#include <unordered_map>

using namespace std;

int maxsubsetsum(int A[], int size, int index)
{
if (index >= size)
return 0;

int sumone = A[index] + maxsubsetsum(A, size, index + 2);
int sumtwo = A[index+1] + maxsubsetsum(A, size, index + 3);

return max(sumone, sumtwo);
}

int main (int argc, void** argv)
{
int A[ ] = {1, - 1, 3, 8 ,4 };
int size = sizeof(A)/sizeof(int);
cout<<maxsubsetsum(A, size, 0);
_getch();
}``````

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

two problems fixed
1. index+1 creates out of bound scenario
2. not working for {-1, 3, 4} gives 3. It should give 4

``````int _sumadjutant(int a[], int size, int index)
{
int sum1, sum2;
if(index>=size) return 0;
sum1 = ((sum1> (sum1+a[index]))? sum1: sum1+a[index]);
if((index+1)>=size)	return sum1;
sum2 = ((sum2> (sum2+a[index+1]))? sum2: sum2+a[index+1]);
return (sum1>sum2)? sum1:sum2;
}``````

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

@- sameep
how this possible ??
in A[ ] = { 1,2,3,4, 5} max sum i s 1 + 3 + 8 = 12. Here 8 is not there in the input array. did you mean 1 + 3 + 5 = 9 ??

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

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

Solution: Just separate two arrays of odd index and even index. Then use maximum sub-array algorithm to find the highest.

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

#include <iostream>
using namespace std;

class LongestSum {

private:

long _findSum ( int* array, int startIndex, int endIndex ) {
if ( startIndex == endIndex ) {
return array[startIndex];
}

int half = ( startIndex + endIndex ) / 2;
long leftSum = _findSum( array, startIndex, half );
long rightSum = _findSum( array, half + 1, endIndex );

long middleSum = 0L;
int left = half;
int right = half + 1;
long currentSum = middleSum;

while ( left >= startIndex && right <= endIndex ) {
if ( array[left] >= array[right] ) {
currentSum = currentSum + array[left--];
}
else {
currentSum = currentSum + array[right++];
}
if ( currentSum >= middleSum ) {
middleSum = currentSum;
}
}
while ( left >= startIndex ) {
currentSum = currentSum + array[left--];
if ( currentSum >= middleSum ) {
middleSum = currentSum;
}
}

while ( right <= startIndex ) {
currentSum = currentSum + array[right++];
if ( currentSum >= middleSum ) {
middleSum = currentSum;
}
}

long halfMax = ( leftSum > rightSum ) ? leftSum : rightSum;
long max = ( halfMax > middleSum ) ? halfMax : middleSum;
return max;
}

public:

long findSum( int *input, int size ) {

if ( size == 0 ) {
return 0;
}

int halves = size / 2;

int* odd = new int[halves];
int* even = new int[size - halves ];
for ( int i = 0; i< size; i++ ) {
if ( i%2 == 0 ) {
even[i/2]= input[i];
}
else {
odd[i/2] = input[i];
}
}

long maxOdd = _findSum(odd, 0, halves - 1 );
long maxEven = _findSum(even, 0, size - halves -1 );

return ( maxOdd > maxEven) ? maxOdd : maxEven;
};

};

int main(int argc, const char * argv[])
{

LongestSum* sum = new LongestSum();
int size = 7;
int input[7] = { 3,-8,4,8,-4,2,3 };
cout << "Sum is " << sum->findSum(input,size) << endl;

int test2[8] = {1,3,5,-1,12,6,7,11};
cout << "Sum is " << sum->findSum(test2,8) << endl;

int test1[7] = {-50,7,11,2,-1,3,4};
cout << "Sum is " << sum->findSum(test1,size) << endl;

int test[5] = {1, - 1, 3, -8 ,-4 };
cout << "Sum is " << sum->findSum(test,5) << endl;

delete sum;
return 0;
}

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

``````#include <iostream>
using namespace std;

class LongestSum {

private:

long _findSum ( int* array, int startIndex, int endIndex ) {
if ( startIndex == endIndex ) {
return array[startIndex];
}

int half = ( startIndex + endIndex ) / 2;
long leftSum = _findSum( array, startIndex, half );
long rightSum = _findSum( array, half  + 1, endIndex );

long middleSum = 0L;
int left = half;
int right = half + 1;
long currentSum = middleSum;

while ( left >= startIndex && right <= endIndex   ) {
if ( array[left] >= array[right] ) {
currentSum = currentSum + array[left--];
}
else {
currentSum = currentSum + array[right++];
}
if ( currentSum >= middleSum ) {
middleSum = currentSum;
}
}
while ( left >= startIndex ) {
currentSum = currentSum + array[left--];
if ( currentSum >= middleSum ) {
middleSum = currentSum;
}
}

while ( right <= startIndex ) {
currentSum = currentSum + array[right++];
if ( currentSum >= middleSum ) {
middleSum = currentSum;
}
}

long halfMax = ( leftSum > rightSum ) ? leftSum : rightSum;
long max = ( halfMax > middleSum ) ? halfMax : middleSum;
return max;
}

public:

long findSum( int *input, int size ) {

if ( size == 0 ) {
return 0;
}

int halves = size / 2;

int* odd    = new int[halves];
int* even   = new int[size - halves ];
for ( int i = 0; i< size; i++ ) {
if ( i%2 == 0 ) {
even[i/2]= input[i];
}
else {
odd[i/2] = input[i];
}
}

long maxOdd = _findSum(odd, 0, halves - 1 );
long maxEven = _findSum(even, 0, size - halves -1 );

return ( maxOdd > maxEven) ? maxOdd : maxEven;
};

};

int main(int argc, const char * argv[])
{

LongestSum* sum = new LongestSum();
int size = 7;
int input[7] = { 3,-8,4,8,-4,2,3 };
cout << "Sum is " << sum->findSum(input,size) << endl;

int test2[8] = {1,3,5,-1,12,6,7,11};
cout << "Sum is " << sum->findSum(test2,8) << endl;

int test1[7] = {-50,7,11,2,-1,3,4};
cout << "Sum is " << sum->findSum(test1,size) << endl;

int test[5] = {1, - 1, 3, -8 ,-4 };
cout << "Sum is " << sum->findSum(test,5) << endl;

delete sum;
return 0;
}``````

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

I think this will not work in the case of:
1,-1,3,8,4 as seperating odd index and even index would result to:
1,3,4=> sum 8
-1,8=> sum 7
So max of two that is sum 8 but max sum is 9 for 1,8 of odd and even index.

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

``````public class Facebook
{
public static int maxSum(int[] arr, int i)
{
if (arr.length > i)
{
if (arr[i] > 0)
return max(arr[i] + maxSum(arr, i + 2), maxSum(arr, i + 1));
else
return max(maxSum(arr, i + 2), maxSum(arr, i + 1));
}

return 0;
}

public static int max(int a, int b)
{
if (a > b)
return a;
else
return b;
}

public static void main(String[] args)
{
int[] arr = {1,3,5,-1,12,6,7,11 };
System.out.println(maxSum(arr, 0));

}
}``````

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

{-4, -5, -3, -9, -4}

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

If I am understanding the problem right, then it means that the elements we consider for optimal output shouldn't be continous (any two numbers). Hence only alternate numbers are supposed to be tried.
e.g [A,a,B,b,C,c,D,d]
Then we need to find max contiguous sum in [A,B,C,D] and in [a,b,c,d] and then print the max of the two.

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

suppose array is -1,-2,-3,4,6,7,8
then according to you max sum is -1,-3,6,8=10
and -2,4,7 =9 then max sum is 10 but max sum is 14 here that is 6+8

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

@vgeek: I think you miss read it. I think @Leaner ask the right question, acording to him the maxum in -1. -3, 6, 8 is 6 + 8 = 14 (not 10 as you pointed out). And since the question is confusing, he want to make it clear. For me I still don't fully undestand the question

Comment hidden because of low score. Click to expand.
-2

The max sum of -1,-2,-3,4,6,7,8 is simply the sum of the positive values i.e., 4+6+7+8!!

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

Assume M(i) represents maximum sum from 1 to i without selecting two contiguous numbers.
Base conditions
A[1] if i=1
Max{A[1],A[2]} if i=2

if i > 2
Max{ A[i] + M(i-2) , M(i-1)}
On this we can write recessive DP program as:

``````int maxsum(int A[], int n)
{
int M[n];
M[0]=a[0];
m[1] = (A[0]>A[1] ? A[0] : A[1]);
for(i=2;i<n;i++)
M[i]=(M[i-1]>M[i-2] + A[i] ? M[i-1] : M[i-2]+A[i]);
return M[n-1];
}``````

Time complexity O(n)

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

This will not work correctly if sequence contains -ve numbers.
Ex: -1, -2, -3, 4, 5

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

#include<stdio.h>
int max_sum(int a[],int n)
{
if(n==0) return;
if(n==1) return a[0];
if(n==2) return a[0]>a[1]?a[0]:a[1];
int s[n];
s[0]=a[0];
s[1]=a[1];
int max=s[0];
int i=0;
for(i=2;i<n;i++)
{
if(a[i]+max>a[i])
s[i]=a[i]+max;
if(s[i-1]>max)
max=s[i-1];
}
return max>s[n-1]?max:s[n-1];
}
void main()
{
int a[]={4,1,6,9,-1,-2,8};
int n=sizeof(a)/4;
printf("%d\n",max_sum(a,n));
}

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

Your code is good but wont handle condition like {-50,7,11,2,-1,3,4}
The o/p of your code will be 13 but the real answer is 11+4=15

else
s[i]=a[i];
to the first if

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

Pseudo code :

``````int maxsubsetsum(int* lst, int numItems) {
if (numItems < 1 || NULL == lst ) {
return -1;
} else if (numItems == 1) {
return lst[0];
}
else if (numItems == 2) {
return Max(lst[0], lst[1]);
}
else if (numItems == 3) {
return Max(lst[0], lst[1], lst[2], lst[0]+lst[2]);
}

int S[numItems] = {0};
S[0] = lst[0];
S[1] = lst[1];
S[2] = Max(lst[0], lst[2], lst[0]+lst[2]);

for (int i = 3; i < numItems; i++) {
int subMax = Max(S[i-2], S[i-3])
S[i] = Max(lst[i], subMax, subMax+lst[i]);
}
return Max(S[numItems-1], S[numItems-2]);
}``````

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

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

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

Guys, I got bit confused here . I mean the subset of the given set without adjacent number included. Its clear case for me that:-
1> add all value in even place and store in variable 1 ,
2> add all value in odd place and store in variable 2.
Now whichever is greater sum return it.
Is it what the question is asking for ?

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

array has negative numbers so consider this case:
{1, - 1, 3, -8 ,-4 }
1+3-4 = 0
-1-8 = -9
according to you the answer would be 1,3,-4 but answer should be 1+3 only.
You need to return maximum.

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

Okei that before adding up the number make sure that negative number should not be taken into consideration.

I mean its still stands the same procedure with O(n) complexity ?

Actually I don't see the need of usage of DP at all here. Of course you can beautify with the implementation.

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

@hprem991: Your logic would be simplest here.Sometimes it is basic thinking which helps in solving 'at first glance complex looking' problems.

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

@hprem991: sorry downvoting.Your startegy won't work for negative numbers:
-1 -2 -3 -4

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

@Aka .. Lol .. Haha Well I am not here to earn Votes, Which I got enough but I understand your doubt about all array being negative numbers right.. Than neither of the above mentioned DP soln handles this Special scenario.

However, I assume that too ain't an issue coz, when U summarize all the value it ends up same thing. and our math comparision operator is enough to handle this. I mean -1 is still bigger than -2 . ;)

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

Solution: Take input array of n. Separate odd index and even index and save it in 2 separate arrays. Then use maximum sub-array algorithm to find the highest for both the arrays.

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

Will this solution fail in any situation:

public static void main(String[] args) {
int arr[]={100,24,25,11,50};
int n= arr.length;
int sum=0;
for(int i=0; i<n;i++){
int temp=arr[i];
if((i+2)<n)
temp+= arr[i+2];

// System.out.println(temp);
if(temp>sum){
sum=temp;
}

}

System.out.println(sum);

}

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

Another very good approach

``````int maximumSum(int arr[])
{
int size = sizeof(arr)/sizeof(arr[0]);
int incl = arr[0];
int excl = 0, excl_new;
for(int i = 1; i < size; i++)
{
excl_new = incl > excl ? incl : excl;
incl = excl + arr[i]; // sum including current element
excl = excl_new; // sum excluding current element
}
return (incl > excl ? incl : excl);
}``````

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

Nice solution. However it does not work for an array of all -Ve numbers. This can be easily addressed by preceeding this function with a check to see if the array is of all -ve numbers, and if so do a linear search and find the maximum element.

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

Yes, in case of all negative numbers we need special check here.

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

I don't understand how do you deal with the fact that selected elements should not be adjacent?

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

So the dynamic programming solution takes O(N square); is there a better solution?

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

See my solution above.

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

Hi,guys,I do not quite understand this question.What do u mean by adjacent numbers. in the test case,A[ ] = {1, - 1, 3, 8 ,4 },numbers 1,8,4 seems to be not adjacent,why the result is not 1+8+4 but 1+8,can somebody tell me why

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

Test

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

``````int find_maxsum(int *a,int n)
{
int i=0;
int prev_sum=0,sum=0,t;
while(i<n)
{
if(prev_sum+a[i]<a[i])
{
//printf("helloo");
sum=a[i];
}
else if(prev_sum+a[i]>sum)
{
//printf("hii");
t=sum;
sum=prev_sum+a[i];
prev_sum=t;
i++;
continue;
}

i++;
prev_sum=sum;
}
return sum;
}
int find_maxsum(int *a,int n)
{
int i=0;
int prev_sum=0,sum=0,t;
while(i<n)
{
if(prev_sum+a[i]<a[i])
{
//printf("helloo");
sum=a[i];
}
else if(prev_sum+a[i]>sum)
{
//printf("hii");
t=sum;
sum=prev_sum+a[i];
prev_sum=t;
i++;
continue;
}

i++;
prev_sum=sum;
}
return sum;
}
int find_maxsum(int *a,int n)
{
int i=0;
int prev_sum=0,sum=0,t;
while(i<n)
{
if(prev_sum+a[i]<a[i])
{
//printf("helloo");
sum=a[i];
}
else if(prev_sum+a[i]>sum)
{
//printf("hii");
t=sum;
sum=prev_sum+a[i];
prev_sum=t;
i++;
continue;
}

i++;
prev_sum=sum;
}
return sum;
}``````

I tried to keep previous sum...and current sum. this is working as far as i have tested.

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

why cant we use the greedy approach here..start with the highest number, then the second largest if it is not adjacent with the highest and so on...

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

in python; works for the three examples.

``````RawSequence = raw_input('Please enter sequence of numbers separated by space:  ')
Seq = map(float, RawSequence.split())

SumMax = 0
while len(Seq) > 0:
SumMax += max(Seq)

if Seq.index(max(Seq))-1 < 0:
LowerBound = 0
else:
LowerBound = Seq.index(max(Seq))-1

if Seq.index(max(Seq))+2 > len(Seq):
UpperBound = len(Seq)
else:
UpperBound = Seq.index(max(Seq))+2

del Seq[LowerBound:UpperBound]

print "The sum is", SumMax``````

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

This can be solved easily in linear time and with constant storage using dynamic programming

the main idea is if we have an array like this [1, - 1, 3, 8 ,4, 0, 11, 3, 4, 20], we want to partition that array into smaller sub arrays around negative or zero elements as negative elements and zeros can not contribute to the maximum sum

so this array should be partitioned into [1], [3, 8, 4], [11, 3, 4, 20]
Then we will find the maximum possible sum in each sub array and add it to the total sum

which should be (1) + (3 + 4) + (3 + 20)

We will assume that the maximum sum for an array of all negative numbers will be zero, otherwise, code can be easily modified to find the non-positive number nearest to zero and return it.

could for this should be something like

``````int maxSum(int *A, int length)
{

// Sum of elements with odd index in the current sub-array
int currSum1 = 0;

// Sum of elements with odd index in the current sub-array
int currSum2 = 0;

// Total maximum sum reached so far
int currMaxSum = 0;

for(int i = 0; i < length; ++i)
{
int value = A[i];

// if the current element is non-positive then add the current
// maximum sum to start working on the next sub-array
if(value <= 0)
{
currMaxSum += max(currSum1, currSum2);
currSum1 = 0;
currSum2 = 0;
}
else if (i & 0x1)	// odd index
{
currSum2 += value;
}
else
{
currSum1 += value;
}

}

return currMaxSum;

}``````

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

Use modified version of Kadane algorithm to find max subarray sum and run it two times: starting from 0 and starting from 1. So the space complexity is constant, runtime O(N). This version also outputs numbers, participated in sum:

``````#include <iostream>
#include <vector>
#include <limits>
#include <algorithm>

struct Result
{
std::vector<int> path;
int last;
int sum;

void solve(std::vector<int> const & values, int start)
{
bool initialized = false;
int maxSoFar = std::numeric_limits<int>::min();
int prevIdx = -1;
last = -1;

path.resize(values.size(), -1);

for (int i = start; i < values.size(); ++i) {
int sumHere = maxSoFar + values[i];

if (sumHere <= values[i] || !initialized) {
prevIdx = -1;
sumHere = values[i];
initialized = true;
}

if (sumHere > maxSoFar && (prevIdx == -1 || i - prevIdx > 1)) {
maxSoFar = sumHere;
path[i] = prevIdx;
prevIdx = i;
last = i;
}
}

sum = maxSoFar;
}
};

int main()
{
std::vector<int> values;

int value;
while (std::cin >> value) {
values.push_back(value);
}

Result res1;
res1.solve(values, 0);
Result res2;
res2.solve(values, 1);

Result * res = res1.sum > res2.sum ? &res1 : &res2;

std::cout << res->sum << std::endl;

int last = res->last;
while (last != -1) {
std::cout << values[last] << ' ';
last = res->path[last];
}

std::cout << std::endl;

return 0;
}``````

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

``````def dpMaxSum(elements):
keyFunc = lambda x: (x[0], not x[1])

dp = [(0, False) for i in xrange(len(elements))]
for i, v in enumerate(elements):
if i == 0:
dp[i] = max([(0, False), (v, True)], key=keyFunc)
elif i == 1:
dp[i] = max([(dp[0][0], False), (v, True)], key=keyFunc)
else:
candidates = [(dp[i - 2][0], False),
(dp[i - 2][0] + v, True),
(dp[i - 1][0], False)]
if not dp[i - 1][1]:
candidates.append((dp[i - 1][0] + v, True))
dp[i] = max(candidates, key=keyFunc)

# print dp
return dp[-1][0]

print dpMaxSum([1, 5, 3, 9, 4])
print dpMaxSum([1, 2, 3, 4, 5])
print dpMaxSum([1, -1, 3, 8, 4])``````

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

``````import java.io.*;

class subsetsum
{
static int l,arr[]={1,3,5,-1,12,6,7,11},max=0;

public static void main(String args[]) throws IOException
{

l=8;
int sum=0,i=0;
max_sum(sum,i);
System.out.println(max);
}

static void max_sum(int sum,int i)
{
if(i>l-1)
{
max=max>sum?max:sum;
return;
}

if(arr[i]>0)
max_sum(sum + arr[i],i+2);
else
max_sum(sum ,i+2);

if(i< l-1)
{
if(arr[i+1]>0)
max_sum(sum + arr[i+1],i+3);
else
max_sum(sum,i+3);

}
}``````

}

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

``````#include<iostream.h>
#include<conio.h>

int max_index(int A[], int size)
{
int i,t = 0;
for(i = 0; i<= size-1; i++)
{
if(A[i]>A[t]) t = i;
}
return t;
}

int main()
{
int A[20],B[20],T[20],n1,n2,sum;
//A = {} ; n1 =
int i,j,temp;
n2 = 0; sum = 0;
int max,val;
cout<<"Enter n1 : "; cin>>n1;
cout<<"Enter "<<n1<<" numbers : ";
for(i = 0; i<n1; i++) cin>>A[i];
for(i = 0; i<n1; i++) {B[i] = 0; T[i] = A[i];}

for (i = 0; i<n1; i++)
{
max = max_index (T,n1);
val = A[max];
T[max] = 0;
if(val<=0) continue;

if( ((max == n1-1) && B[max-1]==0)  || ((max==0)&&B[max+1]==0))
{
B[max] = 1; //assume prev member is not added
n2++;
continue;
}
if(val>(A[max-1]+A[max+1])||B[max+2]||B[max-2])
{
if(!(B[max-1] || B[max+1])){
B[max] = 1; //assume prev member is not added
n2++;
continue;
}
}
}

cout<<"{";
for(i = 0; i<n1;i++)
{
if(B[i]) {
sum += A[i];
cout<<A[i]<<",";
}
}
cout<<"\b }"<<endl<<sum;

getch();
return 0;
}``````

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

O(n) time, O(n) memory:

``````public static int maxSum(int[] arr) {
int[] maxSumIncl = new int[arr.length];//max sum so far including i-th element
int[] maxSumExcl = new int[arr.length];//max sum so far including i-th element
maxSumIncl[0] = Math.max(0, arr[0]);
maxSumIncl[1] = Math.max(0, arr[1]);
maxSumExcl[1] = maxSumIncl[0];
for (int i = 2; i < arr.length; i++) {
maxSumIncl[i] = Math.max(maxSumIncl[i - 2], maxSumExcl[i - 1]) + Math.max(0, arr[i]);
maxSumExcl[i] = Math.max(maxSumIncl[i - 1], maxSumExcl[i - 1]);
}
return Math.max(maxSumIncl[arr.length - 1], maxSumExcl[arr.length - 1]);
}``````

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

``````int count2(const vector<int> & vec ){
if(vec.size() == 0)
return 0;
else if(vec.size() == 1){
return vec[0] >0 ? vec[0] : 0;
}
else if(vec.size() == 2){
int result = vec[0] > vec[1] ? vec[0] : vec[1];
if(result > 0)
return result;
else
return 0;
}

int max = vec[0] > 0 ? vec[0] : 0;
int result = INT_MIN;
vector<int> d(vec.size());
d[0] = vec[0] >0 ? vec[0] : 0;
d[1] = vec[0] > vec[1] ? vec[0] : vec[1];

for(int i=2;i<vec.size();i++){
int t = i-2;
if(max < d[t])
max = d[t];
if(vec[i]>0)
d[i] = vec[i] + max;
else
d[i] = max;
}

for(int i=0;i<d.size();i++){

if(result < d[i])
result = d[i];
}

return result;
}``````

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

Build yourself a max priority queue that accepts a basic struct of two values: the integer value from the original set (which will also be used for comparison within the priority queue), and its index in the original array. Then, as you remove each largest value from the priority queue, you'll have its original index handy. You'll also want to construct a second data structure to keep track of used indexes (be it an array of booleans, or a HashSet<int> of used indexes). If that second data structure deems you clear to use the most recent value removed from the priority queue, apply it toward your sum, mark that index as used, rinse and repeat.

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

This solution seems to be quite clear:

``````public static int bestSum(int[] a){
int res_1=0;
int res_2=0;
for (int i=0; i<a.length; i++){
int temp = Math.max(res_1, a[i] >0 ? res_2+a[i] : res_2);
res_2=res_1;
res_1=temp;
}return res_1;``````

}

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

``````static class Solution{
public static int[] array={-1, -1, -3, 8 ,40};
public static int[] flags=new int[array.length+2];
public static int[] maxSumValues = new int[array.length+2];
public static void main(String[] args){
System.out.println(MaxSum(0));
}

public static int MaxSum(int l){
if(flags[l]==1)
return maxSumValues[l];
if(l+2<array.length)
maxSumValues[l+2]=MaxSum(l+2);
else
maxSumValues[l+2]=0;
flags[l+2]=1;
if(l+1<array.length)
maxSumValues[l+1]=MaxSum(l+1);
else
maxSumValues[l+1]=0;
flags[l+1]=1;
return Math.max(array[l]+maxSumValues[l+2],maxSumValues[l+1]);
}
}``````

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

Dynamic programming solution :
guys please check this code & let me know ...

``````/*
suppose you are given an array of int. for example A[ ] = {1, - 1, 3, 8 ,4 } maximize the sum of subset such that if you include the number in sum, you may not use adjutant numbers to count in sum. so in the example above the max sum is 1+ 8 = 9;
in A[ ] = { 1, 5, 3, 9, 4 } the max sum is 5 + 9 = 14.
and in A[ ] = { 1,2,3,4, 5} max sum i s 1 + 3 + 5 = 9
Developed By: Suman Roy
Email: email.suman.roy@gmail.com
Dynamic prog approach
*/
#include<iostream>
using namespace std;
int Max( int a , int b){
int high;
a>b?high=a:high= b ;
return high;
}
int *sum=new int[10];
int i=0;
int Sum( int *array , int length ){

if ( length <0 ) return -999;
if ( sum[ length ] !=999 ) return sum[ length ];
if ( array[length]> 0 ){
if ( Sum ( array , length - 2 ) >= 0 )
sum[length]=Max( (array[length] + Sum( array , length - 2 ) ), Sum ( array , length -1 ) );
else sum[ length ] = Max ( array [ length ] , Sum ( array , length - 1 ) );
}
else sum[length ]=Max(Max ( array[length] ,Sum(array , length-2 ) ), Sum(array , length - 1) );
return sum[length];
}

int main(){
int array1[]={100,-4,6,125,-5,4,-15};
int length=7;
for ( int i=0 ; i<length ; i++) sum[i]=999;
int sum_res=Sum(array1 , length -1 );
std::cout<<"Sum="<<sum_res<<std::endl;
for ( int ii=0 ; ii<length ; ii++)
std::cout<<sum[ii]<<":";
return 0;
}``````

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

I solved this , posted without logging in.

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

``````int findMaxSum(int arr[], int n)
{
int incl = arr[0];
int excl, excl_new;
for(int i = 1; i < n; i++)
{
excl_new = incl > excl ? incl : excl;
incl = excl + arr[i];
excl = excl_new;
}
return (incl > excl ? incl : excl);
}``````

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

It prints or just tells us the maximum sum not a sequence geeksforgeeks..:P

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

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

Why not just split the array into parts such that non contiguous elements form part of each array. So now u have two arrays and need to find the max subsequence. This is an O(n) operation where n is ideally half the size of the total number of elements in the array.

i.e. O(n1) + O(n2) or avg case = O(N/2) and worst case of O(N).

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

Solution in ruby:

``````#!/usr/bin/env ruby

require 'pp'

def max_sum num_array

retval = []

def get_max_sum num_array, retval, sum = 0

# Sum the element and recurse with the ! _ ! element
if num_array != nil
sumtmp = sum + num_array[0]
if num_array.size > 2
new_array = num_array[2,num_array.size-1]
get_max_sum new_array,retval, sumtmp
get_max_sum nil,retval,sumtmp
end
end

# Sum the element and recurse with the ! _ _ ! element
if num_array != nil and num_array.size > 1
sumtmp = sum + num_array[1]
if num_array.size > 3
new_array = num_array[3,num_array.size-1]
get_max_sum new_array,retval, sumtmp
else
get_max_sum nil,retval,sumtmp
end
end

# If == nil, no more to process and push the value
if num_array == nil
retval << sum
end

end

get_max_sum num_array,retval

return retval.max

end

pp max_sum [1,5,3,9,4]``````

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

``````import java.util.*;
import java.io.*;

public class MaxSum{
public static void main(String[] args){
InputStream in = System.in;
Scanner scanner = new Scanner(in);
while(scanner.hasNextLine()){
int[] ints = getInts(scanner.nextLine());
Wrapper[] wrappers = new Wrapper[ints.length];
for(int i=0;i<ints.length;i++){
Wrapper wrapper = new Wrapper(i, ints[i]);
wrappers[i] = wrapper;
}
Arrays.sort(wrappers);
solve(wrappers);
}
scanner.close();
}

//big values should be up front
static void solve(Wrapper[] wrappers){
ArrayList<Wrapper> list = new ArrayList<Wrapper>();
for(int i=0;i<wrappers.length;i++){
Wrapper wrapper = wrappers[i];
if(!isNextTo(list, wrapper)){
}
}
int sum = 0;
for(int i=0;i<list.size();i++){
Wrapper wrapper = list.get(i);
System.out.print(wrapper.value);
if(i!=list.size()-1){
System.out.print(" + ");
}
sum+=wrapper.value;
}
System.out.println(" = "+sum);
}

static boolean isNextTo(ArrayList<Wrapper> list, Wrapper wrapper)
{
for(Wrapper w : list)
{
if(w.index==wrapper.index-1 || w.index==wrapper.index+1){
return true;
}
}
return false;
}

static int[] getInts(String line){
String[] str = line.split(" ");
int[] ints = new int[str.length];
for(int i=0;i<str.length;i++){
ints[i] = Integer.parseInt(str[i]);
}
return ints;
}

static class Wrapper implements Comparable<Wrapper>{
public int index;
public int value;
public Wrapper(int index, int value){
this.index = index;
this.value = value;
}
public int compareTo(Wrapper other){
int diff = value - other.value;
if(diff<0) return 1;
else if(diff>0) return -1;
return 0;
}
}
}``````

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

``````public static int maxsum(int[] a, int i, boolean skip)
{
int sum = 0;

if (i == a.length)
return sum;

if (!skip)
{
sum = sum + a[i];
sum = sum + maxsum(a, i + 1, true);
}
else
sum = sum + Math.max(maxsum(a, i + 1, false), maxsum(a, i + 1, true));

return sum;
}

public static void main(String[] args)
{
int[] a = { 1, 2, 3, 4, 5 };
int index = 0;

System.out.println(Math.max(maxsum(a, index, false), maxsum(a, index, true)));

}``````

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

Linear solution with constant additional memory in JS:

``````var A = [1, 5, 3, 9, 4], partial = [], i;
partial[0] = Math.max(A[0], 0);
partial[1] = Math.max(partial[0], Math.max(A[1], 0));
for (i = 2; i < A.length; i++) {
partial[i % 2] = Math.max(partial[(i - 1) % 2], partial[(i - 2) % 2] + Math.max(A[i], 0));
}``````

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

I just made a small modification to kadane's algorithm and this seems to be working. Any comments will be much appreciated. And, I am guessing it's O(N). Cheers.

``````{
int sequence[5] = {-1, -2, -3, 4, 5};

int max(int a, int b){

return (a>b?a:b);

}

int main(void) {

int i;
int max_now = sequence[1];
int max_final = sequence[1];
int max_now_even = sequence[0];
int max_final_even = sequence[0];
int begin, begin_temp, end =0;
int begin_even, begin_temp_even, end_even=0;

for(i=2;i<sizeof(sequence)/sizeof(int);i++){

if(i%2!=0){

if(max_now < 0){

max_now = sequence[i];
begin_temp = i;

}

else {

max_now += sequence[i];

}

if(max_now > max_final){

max_final = max_now;
begin = begin_temp;
end = i;

}

}

else {

if(max_now_even < 0){

max_now_even = sequence[i];
begin_temp_even = i;

}

else {

max_now_even += sequence[i];

}

if(max_now_even > max_final_even){

max_final_even = max_now_even;
begin_even = begin_temp_even;
end_even = i;

}

}

}

printf("the max subset here is: %d",max(max_final, max_final_even));

return EXIT_SUCCESS;
}``````

}

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

{ public static int findMaxSubArray(int[] A){
if (A.length == 0) return -1;
//tracks the historical max;
int max = A[0];
//tracks the cur max possible path
int sum = 0;
for (int i = 0; i<A.length; i++){
sum = Math.max(A[i],sum+A[i]);
max = Math.max(max, sum);
}
return max;
}
}

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

{ public static int findMaxSubArray(int[] A){
if (A.length == 0) return -1;
//tracks the historical max;
int max = A[0];
//tracks the cur max possible path
int sum = 0;
for (int i = 0; i<A.length; i++){
sum = Math.max(A[i],sum+A[i]);
max = Math.max(max, sum);
}
return max;
}
}

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

This code will be ok.

``````int Dp(std::vector<int> & v) {
int n = v.size();
std::vector<int> dp(n, 0);
if (n == 0) return 0;
else if (n == 1) return v[0];
else if (n == 2) return std::max(v[0], v[1]);
else {
dp[0] = v[0];
dp[1] = std::max(v[0], v[1]);
int rs = std::max(dp[0], dp[1]);
int max = dp[0];
for (int i = 2; i < n; i++) {
dp[i] = std::max(v[i], v[i] + max);
max = std::max(max, dp[i - 1]);
rs = std::max(rs, dp[i]);
}
return rs;
}
}``````

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

O(N) dynamic programming solution:
Let dp[i][0] - answer for first i elements with no i-th element included,
dp[i][1] - answer for first i elements with i-th element included.
Then dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]) - if last element is not included lets select max from 2 possible answers for i - 1.
dp[i][1] = d[i - 1][0] + a[i] - select answer when prev is not included + current value.
Here is implementation in Java:

``````int n = in.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = in.nextInt();
}

int[][] dp = new int[n + 1][2];
for (int i = 1; i <= n; i++) {
dp[i][1] = dp[i - 1][0] + arr[i - 1];
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
}
out.println(Math.max(dp[n][1], dp[n][0]));``````

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

here the problem is, to add the next biggest no, we need to check that it is not an adjacent element of already added elements. This will take more time.

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.