Amazon Interview Question Software Engineer / Developers
This fails for even a very simple case of all positive numbers.
Consider {1,2}
{3, 8, 2}
This cannot be correct, just consider this example that noob_coder mentioned.
{1,2}
max sum will be 1+2=3. But it you use LOL's algo, it finds max of 1,2 and returns 2. So, it fails!
Got confused. Either of us misunderstood the problem, I guess.
For first input, max is sum[1] = 2, you can't take both a[0] and a[1] as they are adjacent.
For 2nd input, sum[0] = 3, sum[1] = 8, sum[2] = max(2+sum[0], sum[1])=8. What's wrong there?
well, there is no specification what should be output for all -ve numbers. It could be either 0, or largest -ve number.Above approach gives 0, which seems a valid output (means a subset of size 0).
There is no point in changing the question and answering..The question clearly says +ve -ve randomly (random could be zero) distributed..if you can solve for +ve why not for -ve.
BTW, What is the output of your problem..is it sum[i] for i integers?
Yes, sum[i] stores the max value. I'd appreciate if you could give a counter example where above recurrence fails. Thanks.
what should be the output for 10 5 -8 -19 then... i guess it should be 10.. your sum[3] gives 5.
Hmm... you are right. I tweak above recurrence as :
sum[i] = max (a[i], a[i] + sum[i-2], sum[i-1], sum[i-2]) ; for i >=2
The idea is that we've below options:
1. don't take a[i], then max (sum[i-2], sum[i-1]) is the answer
2. consider taking a[i], if it's -ve, don't take..if it's positive consider a[i] + sum[i-2].
Here is my solution :
public int largestSumOfSubsets(List list) {
//arr could contain duplicates
int sum1 = getSums(list, 0).sum;
int sum2 = getSums(list, 1).sum;
if (sum1 > sum2) {
return sum1;
}
return sum2;
}
public SumItem getSums(List list, int index) {
ArrayList<ArrayList<Integer>> finalList1 = new ArrayList<ArrayList<Integer>>();
SumItem sumItem = new SumItem(finalList1, 0);
if (index >= list.size()) {
ArrayList<Integer> tempArr = new ArrayList<Integer>();
finalList1.add(tempArr);
} else {
sumItem = getSums(list, index + 2);
finalList1 = sumItem.list;
int item = (Integer)list.get(index);
ArrayList<ArrayList<Integer>> moreSubsets = new ArrayList<ArrayList<Integer>>();
for (ArrayList<Integer> subset : finalList1) {
ArrayList<Integer> newset = new ArrayList<Integer>();
newset.addAll(subset);
newset.add(item);
int tempsum = add(newset);
if (tempsum > sumItem.sum) {
sumItem.sum = tempsum;
}
moreSubsets.add(newset);
}
finalList1.addAll(moreSubsets);
}
return sumItem;
}
private class SumItem {
ArrayList<ArrayList<Integer>> list;
int sum;
public SumItem(ArrayList<ArrayList<Integer>> list, int sum) {
super();
this.list = list;
this.sum = sum;
}
}
private int add(ArrayList<Integer> newset) {
int sum = 0;
Iterator<Integer> iter = newset.iterator();
while (iter.hasNext()) {
sum += iter.next();
}
return sum;
}
//Test Program
public static void main (String[] args) {
List randomsortedList = new ArrayList();
randomsortedList.add(50);randomsortedList.add(100);
randomsortedList.add(-13);randomsortedList.add(12);randomsortedList.add(-5);
randomsortedList.add(-2);randomsortedList.add(-20);randomsortedList.add(-3);
randomsortedList.add(100);
System.out.println(randomsortedList);
System.out.println(largestSumOfSubsets(randomsortedList));
}
This is little complex, I think he was looking for a simpler approach. Any other approach possible?
Putting the code with induntation
public int largestSumOfSubsets(List list) {
//arr could contain duplicates
int sum1 = getSums(list, 0).sum;
int sum2 = getSums(list, 1).sum;
if (sum1 > sum2) {
return sum1;
}
return sum2;
}
public SumItem getSums(List list, int index) {
ArrayList<ArrayList<Integer>> finalList1 = new ArrayList<ArrayList<Integer>>();
SumItem sumItem = new SumItem(finalList1, 0);
if (index >= list.size()) {
ArrayList<Integer> tempArr = new ArrayList<Integer>();
finalList1.add(tempArr);
} else {
sumItem = getSums(list, index + 2);
finalList1 = sumItem.list;
int item = (Integer)list.get(index);
ArrayList<ArrayList<Integer>> moreSubsets = new ArrayList<ArrayList<Integer>>();
for (ArrayList<Integer> subset : finalList1) {
ArrayList<Integer> newset = new ArrayList<Integer>();
newset.addAll(subset);
newset.add(item);
int tempsum = add(newset);
if (tempsum > sumItem.sum) {
sumItem.sum = tempsum;
}
moreSubsets.add(newset);
}
finalList1.addAll(moreSubsets);
}
return sumItem;
}
private class SumItem {
ArrayList<ArrayList<Integer>> list;
int sum;
public SumItem(ArrayList<ArrayList<Integer>> list, int sum) {
super();
this.list = list;
this.sum = sum;
}
}
private int add(ArrayList<Integer> newset) {
int sum = 0;
Iterator<Integer> iter = newset.iterator();
while (iter.hasNext()) {
sum += iter.next();
}
return sum;
}
//Test Program
public static void main (String[] args) {
List randomsortedList = new ArrayList();
randomsortedList.add(50);randomsortedList.add(100);
randomsortedList.add(-13);randomsortedList.add(12);randomsortedList.add(-5);
randomsortedList.add(-2);randomsortedList.add(-20);randomsortedList.add(-3);
randomsortedList.add(100);
System.out.println(randomsortedList);
System.out.println(largestSumOfSubsets(randomsortedList));
}
Except am missing something here.
Traverse the array twice picking out the positive integers alternatively.
e.g
array : 1,2,-1,4,-1,2,1,3
0,1, 0,1, 0,1,0,1
First pass : get the sum of the positive array elements assigned zero.
second pass : get the sum of the positive array elements assigned ones.
int findMax(int ind)
{
if(ind >= n) return 0;
int mx = -INF;
mx >?= findMax(ind+1);
mx >?= arr[ind] + findMax(ind+2);
return mx;
}
int positivesum =0 , neg ;
take a window of three numbers and find the max in those . whichever a[index] is the max,add it to the positive sum , add 2 to index and start the next window . If the max is a negative ,store it in a variable, when another negative max encountered store the max of both . When any positive max is encountered change the value of neg to 0 .
@LOL
Your code fails for 2,-2,-2,5,15 for which your code gives 15 as the answer instead of 17.
I have changed your code slightly :
sum[0]=sum[1]=max(a[0],a[1]);
sum[i]=max(a[i],s[i-1],s[i-2],a[i]+s[i-2])
The answer will be in sum[n] (n=no. of elements). This will also work for all negative numbers.
If anyone finds any mistake in this code please show.
Don't you think that we could simplify the recurrence to :
if (a[i] < 0) sum[i] = sum[i-1]
[because, sum[i-2] <= sum[i-1])
if (a[i] > 0) sum[i] = max (a[i], a[i]+sum[i-2], sum[i-1])
Pls verify if this is correct.
I write in Java. Don't hate. Nonetheless, here's my O(n) solution:
public int findMaxSum(int[] given){
int curSum = given[0];
int maxSum = given[0];
for (int i=1;i<given.length;i++){
if (curSum >=0){
curSum += given[i];
if (maxSum < curSum)
maxSum = curSum;
}
}
return maxSum;
}
It's worked for all the test cases I could think of.
<pre lang="" line="1" title="CodeMonkey79650" class="run-this">public static int findMaxSum(int[] numbers) {
if (numbers.length == 0) {
return 0;
} else if (numbers.length == 1) {
return Math.max(0, numbers[0]);
} else if (numbers.length == 2) {
return Math.max(0, Math.max(numbers[0], numbers[1]));
} else if (numbers.length == 3){
int innerSum = Math.max(0, Math.max(0, numbers[1]));
int outerSum = Math.max(0, Math.max(0, numbers[0]) + Math.max(0, numbers[2]));
return Math.max(innerSum, outerSum);
} else {
for (int i = 3; i < numbers.length; i++) {
int curNum = Math.max(0, numbers[i]);
int secondLastNum = Math.max(0, numbers[i-2]);
int thirdLastNum = Math.max(0, numbers[i-3]);
numbers[i] = Math.max(curNum + secondLastNum, curNum + thirdLastNum);
}
return Math.max(numbers[numbers.length - 1], numbers[numbers.length - 2]);
}
}</pre><pre title="CodeMonkey79650" input="yes">I think this should run in O(n) and handle all cases.</pre>
I hope this works out to be the O(n) way ?
public long findMax(int index){
long res = 0;
for(int i=0; i<=index; i++){
if(arr[i] >= 0){
res += arr[i];
i++;
}
}
return res;
}
Input Array { 1, -2, -4, 3, -5, -1, 2, 4, 6, -2 }
for index = 9 -> Max sum = 12
for index = 6 -> Max sum = 6
@Vip - Since you algo always adds the arr[i] >= 0 and skips arr[i+1] , it seems not to produce correct result for the following sequence
arr = {-1,2,4,1} - algo would add 2 and 1 and skips 4
But adding 4 would result in Maximum sum.
thnks seeksree. you are correct, it'll not always return the highest result
For the given subset
-1 + 4 + 1 = 4
2 + 1 = 3
I was taking only positive numbers in consideration, ignoring -ive numbers totally :P
& by -1 + 4 + 1 I meant, 'not taking adjacent terms'
i.e 4 alone will be the highest sum (?!?)
I think this shud sort out all ur problems this takes care of ur -ve nums too .. have a look
{
public static void main(String[] args){
int num[]; //array of +ve n -ve nums
int sum_first = findLargestSum(nums,0,len);
int sum_second = findLargestSum(nums,1,len);
if(sum_first>sum_second)
System.out.println(sum_first);
else
System.out.println(sum_second);
}
static int findLargestSum(int[] nums, int index, int len){
if(index+2>=len)
return nums[index];
int largest_sum =0 ;
int temp_sum;
int count =0;
for(int i=index+2;i<len;i++){
if(count==0)
largest_sum=findLargestSum(nums, i,len);
else
{
temp_sum = findLargestSum(nums, i,len);
if(largest_sum < temp_sum)
largest_sum = temp_sum;
}
count++;
}
if(largest_sum<0 && nums[index]<0){
if(largest_sum>nums[index])
return largest_sum;
else
return nums[index];
}
else if(nums[index]>=0 && largest_sum<0){
return nums[index];
}
else if(largest_sum >=0 && nums[index]<0){
return largest_sum;
}
else
return (nums[index] + largest_sum);
}
int dp[N];
//N= number of elements;
int array[5]={1,2,3,4,5};
int solve(int index){
if(dp[index]!=-INF)return dp[index];
if(index>=N) return 0;
int maxsum=-INF;
for(int i=index;i<N;i++){
maxsum=max(maxsum,array[i]+solve(i+2));
}
return dp[index]=maxsum;
}
int main(){
for(int i=0;i<N;i++) dp[i]=-INF;
cout<<solve(0);
return 0;
}
Am i correct ?
-> If array contains positive and negative both then max subset sum should be sum of all positive number.
-> If it contains all negative. Then max subset sum should be smallest negative number.
-> It it contains all positive. Then sum all of them to get max subset sum.
Please correct me if I am wrong.
?
#include<stdio.h>
/*Function to return max sum such that no two elements
are adjacent */
int FindMaxSum(int arr[], int n)
{
int incl = arr[0];
int excl = 0;
int excl_new;
int i;
for (i = 1; i < n; i++)
{
/* current max excluding i */
excl_new = (incl > excl)? incl: excl;
/* current max including i */
incl = excl + arr[i];
excl = excl_new;
}
/* return max of incl and excl */
return ((incl > excl)? incl : excl);
}
/* Driver program to test above function */
int main()
{
int arr[] = {5, 5, 10, 100, 10, 5};
printf("%d \n", FindMaxSum(arr, 6));
getchar();
return 0;
}
Time Complexity: O(n)
Working Python code that used some of the ideas above:
def max_subset(L):
M = [None]*len(L)
M[0] = max(L[0],0)
M[1] = max(M[0], L[1])
for i in range(2,len(L)):
if M[i-2]==M[i-1]: # element L[i-1] not necessarily used
M[i] = M[i-2] + max(L[i],0)
else: # element L[i-1] used in M[i-1]
M[i] = max(M[i-2]+L[i], M[i-1])
return M[-1]
L = [1, -2, -4, 3, -5, -1, 2, 4, 6, -2]
print max_subset(L)
int maxsum(int arr[],int n)
{
int sum=0;
int i=0;
while(i<n)
{
if(arr[i]>0)
{
int j=i+1,count=0;
while((arr[j]>0)&&(j<n))
{
count++;
j++;
}
printf("%d\n",count);
if(count%2!=0)
{
if((arr[i+1]>0)&&(arr[i+1]>arr[i]))
{
sum=sum+arr[i+1];
i=i+1+2;
}
}
else
{
sum=sum+arr[i];
i=i+2;
}
}
else
{
i++;
}
}
return sum;
}
/*
if the last element is selected (n) then n-1 can't be included
if n is not selected then n-1 can be included
opt[n] = the maximum sum from 1...n
max { arr[n] + opt[n-2], opt[n-1] }
O(N)
*/
public static void maxDp(int arr[]) {
int maxSum[] = new int[arr.length];
maxSum[0] = arr[0] > 0 ? arr[0] : 0;
maxSum[1] = Math.max(arr[1], arr[0]);
for(int i = 2; i < arr.length; i++) {
int inc = arr[i] > 0 ? (arr[i] + maxSum[i-2]) : maxSum[i-2];
maxSum[i] = Math.max(inc, maxSum[i-1]);
}
int i = maxSum.length - 1;
while(i >= 0) {
if(arr[i] > 0) {
if(i < 2 || (arr[i] + maxSum[i-2]) > maxSum[i-2])
System.out.print(arr[i] + " ");
i = i - 2;
} else {
i = i -1;
}
}
}
It can be done in O(1) using below recurrence:
Any catch there?
- LOL May 06, 2011