Yahoo Facebook Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
@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]);
}
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]);
}
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
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];
}
please read the question carefully. "you may not use adjutant numbers to count in sum"
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.
Code is clean and concise, but I think it only works for lists of positive numbers. Counterexample: [8, 7, -2, -2]
Kadence solution should work I guess but only difference would be here we have to consider only adjacent numbers.
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.
@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
#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();
}
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;
}
@- 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 ??
Solution: Just separate two arrays of odd index and even index. Then use maximum sub-array algorithm to find the highest.
#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;
}
#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;
}
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));
}
}
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.
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: 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
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)
#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));
}
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]);
}
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 ?
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.
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: Your logic would be simplest here.Sometimes it is basic thinking which helps in solving 'at first glance complex looking' problems.
@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 . ;)
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);
}
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);
}
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.
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.
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
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;
}
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;
}
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])
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);
}
}
}
#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;
}
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]);
}
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;
}
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.
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]);
}
}
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;
}
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);
}
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).
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]
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;
}
}
}
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)));
}
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));
}
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;
}
}
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;
}
}
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]));
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
Edited to fix the bug as suggested by Celgin
- Murali Mohan June 05, 2013