Yahoo Facebook Interview Question for Software Engineer / Developers


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();
			input.add(intval);
		}

		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

- Murali Mohan June 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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]);
}

- aka June 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

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

- aka June 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
5
of 5 votes

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();
input.add(intval);
}

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

- cengin June 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- aka June 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 votes

@cengin, aka

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

- Murali Mohan June 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- liuml07 June 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- yonatan.graber December 06, 2013 | Flag
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];
}

- tanrei June 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 votes

please read the question carefully. "you may not use adjutant numbers to count in sum"

- Vin June 05, 2013 | Flag
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.

- Anonymous June 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- dc June 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- aka June 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Vin June 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous June 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 votes

@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

- Murali Mohan June 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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.

- Anonymous June 05, 2013 | Flag
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();
}

- sameep June 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 = _sumadjutant(a,size, index+2);
	sum1 = ((sum1> (sum1+a[index]))? sum1: sum1+a[index]);
	if((index+1)>=size)	return sum1;
	sum2 = _sumadjutant(a,size, index+3);
	sum2 = ((sum2> (sum2+a[index+1]))? sum2: sum2+a[index+1]);
	return (sum1>sum2)? sum1:sum2;
}

- tohana June 06, 2013 | Flag
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 ??

- Vin June 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

yes. my bad. corrected.

- sameep June 05, 2013 | Flag
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.

- Rajesh M D June 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

#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;
}

- Anil June 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

#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;
}

- Anil June 06, 2013 | Flag
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.

- vgeek June 06, 2013 | Flag
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));

	}
}

- Jose June 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- Anonymous April 09, 2014 | Flag
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.

- Learner July 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- vgeek July 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 votes

@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

- LinhHA05 July 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 votes

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

- Anonymous July 29, 2013 | Flag
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)

- pirate August 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Rahul September 14, 2013 | Flag
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));
}

- Anonymous June 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

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

- Sabir Ahmed June 05, 2013 | Flag
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]);
}

- Vin June 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

what is adjutant numbers?

- Jackie June 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

adjacent. please fix

- dc June 05, 2013 | Flag
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 ?

- hprem991 June 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- aka June 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- hprem991 June 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- aka June 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- aka June 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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 . ;)

- hprem991 June 05, 2013 | Flag
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.

- Rajesh M D June 05, 2013 | Flag Reply
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);

}

- Ankit Masrani June 05, 2013 | Flag Reply
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);
}

- Nitin Gupta June 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Vinay June 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Nitin Gupta June 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- DukeXar June 07, 2013 | Flag
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?

- IntwPrep June 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

See my solution above.

- Nitin Gupta June 06, 2013 | Flag
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

- ray June 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Test

- anonymous June 06, 2013 | Flag Reply
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.

- Joey June 06, 2013 | Flag Reply
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...

- upasana June 06, 2013 | Flag Reply
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

- Anonymous June 06, 2013 | Flag Reply
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;

}

- usama.fayez June 07, 2013 | Flag Reply
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;
}

- DukeXar June 07, 2013 | Flag Reply
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])

- Anonymous June 09, 2013 | Flag Reply
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); 
                   
             }  
      }

}

- ravi June 10, 2013 | Flag Reply
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;          
}

- Sahil Kamboj June 11, 2013 | Flag Reply
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]);
	}

- Anonymous June 23, 2013 | Flag Reply
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;
}

- gaoxinbo1984 June 25, 2013 | Flag Reply
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.

- Dan Groft June 26, 2013 | Flag Reply
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;

}

- guigou July 09, 2013 | Flag Reply
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]);
		}
	}

- Negar July 14, 2013 | Flag Reply
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;
}

- Anonymous July 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I solved this , posted without logging in.

- email.suman.roy July 17, 2013 | Flag
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);
}

- Nitin Gupta July 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- vgeek July 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Nitin Plz explain your algo..

- Rahul September 14, 2013 | Flag
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).

- Keshy July 30, 2013 | Flag Reply
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]

- Juan Brein August 04, 2013 | Flag Reply
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)){
				list.add(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;
		}
	}
}

- Anonymous August 26, 2013 | Flag Reply
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)));

	}

- Mark August 27, 2013 | Flag Reply
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));
}

- gmetrofun September 18, 2013 | Flag Reply
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;
}

}

- Anonymous September 30, 2013 | Flag Reply
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;
}
}

- OMG Y'all December 17, 2013 | Flag Reply
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;
}
}

- OMG Y'all December 17, 2013 | Flag Reply
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; 
  }
}

- guoliqiang2006 December 30, 2013 | Flag Reply
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.
Finally, answer is max(dp[n][1], dp[n][0]).
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]));

- Acarus November 20, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Vin June 05, 2013 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More