Citrix System Inc Interview Question Dev Leads Dev Leads
Country: India
Interview Type: In-Person
public static void printMaxSum(int[] n){
if(n.length==0)
System.out.println("array has no data");
else if (n.length==1){
System.out.println(n[0]);
System.out.println(n[0]);
}else if (n.length==2){
System.out.println(n[0] + n[1]);
System.out.println(n[0] + " " + n[1]);
}else{
int v1 = (n[0]>n[1])?n[0]:n[1];
int v2 = (n[0]>n[1])?n[1]:n[0];
for(int i=2; i<n.length;i++){
if(n[i]>v1){
v2=v1;
v1=n[i];
}else if(n[i]<v1 && n[i]>v2){
v2=n[i];
}
}
System.out.println(v1 + v2);
System.out.println(v2 + " " + v1);
}
}
public static void printMaxSum(int[] n){
if(n.length==0)
System.out.println("array has no data");
else if (n.length==1){
System.out.println(n[0]);
System.out.println(n[0]);
}else if (n.length==2){
System.out.println(n[0] + n[1]);
System.out.println(n[0] + " " + n[1]);
}else{
int v1 = (n[0]>n[1])?n[0]:n[1];
int v2 = (n[0]>n[1])?n[1]:n[0];
for(int i=2; i<n.length;i++){
if(n[i]>v1){
v2=v1;
v1=n[i];
}else if(n[i]<v1 && n[i]>v2){
v2=n[i];
}
}
System.out.println(v1 + v2);
System.out.println(v2 + " " + v1);
}
}
procedure MaxSum(d; Profit[1...n])
L = array size n + d filled with 0. //Padded d extra element to avoid bound issues
for i 2 n::1 do
in = Profit[i] + L[i + d]
out = Profit[i + 1]
L[i] = max(in; out)
end for
return L[0]
end procedure
This is the Dynamic Programming approach if I am not mistaken. It looks like this is coming from this Back Tracking approach (int C++ since nobody like psuedo code)
The basic idea is to see what's the best you can do including the current element and compare that with what's the best you can do without including it
void MaxSum(int size, int arr[])
{
if(size<=0)
return 0;
if(size==1)
return arr[0];
if(size==2)
return MAX(arr[0],arr[1]);
//include the first element recurse on everything after skipping adjacent
int in=arr[0]+MaxSum(size-2, &arr[2]);
//skip the first one and recurse on everything after it
int out=MaxSum(size-1, &arr[1]);
return MAX(in, out);
}
Now this is NOT the solution the interviewer is looking for but your solution follows from it. The idea is that we store the solution to recursive sub-problems in the results array and thus can look them up instead of recomputing them every time...though I do like your handy trick of padding the array to not have to deal with the base cases like in my recursive solution.
Now to get the actual indexes, just save them as a linked list in as you are calculating the subproblems.
import java.util.ArrayList;
public class MaxSumVal {
public static void main(String[] args) {
Integer[] noArray = {-1,4,5,-2,-6,6};
//Integer[] noArray = {1,0,5,25,-1,4,5,-2,-6,6};
//Integer[] noArray = {-1,-9,-5,0,1,10,-3,5,12,-34};
//Integer[] noArray = {-1};
//Integer[] noArray = {-1,9};
Integer noArrayLen = noArray.length;
Integer finalSum = 0;
ArrayList<Integer> sumValues = new ArrayList<Integer>();
Integer tempVal = 0;
Integer iPlusOneAdjacency = 0;
if(noArrayLen == 1){
//If the number of the values is equal to 1 then the value itself will be the highest
finalSum = noArray[0];
sumValues.add( noArray[0] );
}else if(noArrayLen == 2){
//If the number of the values is equal to 2 then choose the greater value
finalSum = (noArray[0] > noArray[1]) ? noArray[0] : noArray[1];
sumValues.add( finalSum );
}else if(noArrayLen >= 3){
//If the number of the values is equal >= 3 then do the following
for(Integer i=0; i<noArrayLen; i=i+2 ){
//resetting tempVal at the beginning of each loop
tempVal = 0;
if(i-1 > 0 && noArray[i-1] < noArray[i]){
if(i+1 < noArrayLen && noArray[i] > noArray[i+1]){
tempVal = noArray[i];
//we need to check for adjacency only when we select value at i
if(iPlusOneAdjacency == i){
//if adjacency was set then we'll replace the previously set values
//to the current value and subtract that value from te finalSum
if(sumValues.size() > 0){
finalSum -= sumValues.get(sumValues.size() - 1);
sumValues.set(sumValues.size() - 1, tempVal);
iPlusOneAdjacency = 0;
}
}else{
sumValues.add( tempVal );
}
finalSum +=tempVal;
}else{
//An adjacency is always set if an i+1 values is selected
tempVal = noArray[i+1];
//we set the iPlusOneAdjacency value to i+2 as the next loop has the value = i+2
iPlusOneAdjacency = i + 2;
sumValues.add( tempVal );
finalSum += tempVal;
}
}else{
if(i+1 < noArrayLen && noArray[i] > noArray[i+1]){
if(i-1 >0){
tempVal = noArray[i-1];
if(iPlusOneAdjacency == 0){
sumValues.add( tempVal );
finalSum += tempVal;
}else{
iPlusOneAdjacency = 0;
}
}else{
tempVal = noArray[i];
sumValues.add( tempVal );
finalSum += tempVal;
}
}else{
tempVal = noArray[i+1];
iPlusOneAdjacency = i + 2;
sumValues.add( tempVal );
finalSum += tempVal;
}
}
}
}
System.out.println(finalSum);
System.out.println(sumValues);
}
}
I dont know where the semicolon came from in if(i-1 >;0){}, its not in my actual code but still comes up
I noticed that you included negative numbers in your sum. You don't want to do that. Also, I was trying to follow along your code with the below test case and got { 8 11 } = 19 when the max sum = { 4 7 11 } = 22.
{ -1, 4, 8, 7, 1, 3, 11, -1, -1, -1 }
In general I don't think that anyone's greedy algorithm will work because finding the best path requires forward probing an arbitrary distance down the array. I don't think going backwards works for the same reason. I've been foiling myself with test cases like this one that require looking ahead several steps to avoid getting trapped.
I wrote the approach below : it works well with this case as well
{ -1, 4, 8, 7, 1, 3, 11, -1, -1, -1 }
| {0}
| {0}
| {0}
| {11 + 0}
| {3 + 0}
| {1 + 11 + 0}
| {7 + 11 + 0}
| {8 + 1 + 11 + 0}
| {4 + 7 + 11 + 0}
| {greater of next two postive number, if second is negative take only of the first}
= {4 + 7 + 11 + 0} = 22
Let me know if there is any issue.
@John42, just making things clear, what if all the numbers are negative, just choose the one closest to zero?
Think of this as a graph problem.
example: -1, 5, -2, 0
1. Make a graph with nodes equal to number of elements in the array.
2. Connect the edges in this way: -1 can connect to -2 and 0 so there will be a outgoing two outgoing edges to -2 and 0.
Same goes with other nodes i.e. 5 node will be connected to 0 using only one outgoing edge.
3. Once you have the graph ready then nodes values will be equal edge weights.
4. for_each_node {
target = 0 (end of array element)
start = current_node
longest_path = max(longest_path, find_longest_path(graph))
}
return longest_path
here is a c++ code
but i don't know if it can be done in a simpler way
#include <iostream>
using namespace std;
int main()
{
int i,n,*a,sum=0,pospre=0,j,k,sum1,sum2,s=0;
cin>>n;
a=new int[n];
for(i=0;i<n;i++)
cin>>a[i];
i=0;
while(i<n)
{
if(a[i]>0)//is this a positive integer?
{
if(pospre==0)//found the first positive number
pospre=1;
j=i;//trying to find a continuous subarray with no negative ints
while(j<n&&a[j]>0)//is the end due to array end or due to occurrence of -ve num
{
j++;
}
j--;
if(i==j)
{
a[s]=a[i];
s++;
sum=sum+a[i];
}
else{
k=i;
sum1=0;
sum2=0;
while(k<=j)
{
sum1+=a[k];
k++;
if(k<=j)
{
sum2+=a[k];
k++;
}
}
if(sum1>=sum2)//see which sum is greater add that sum and print the numbers contributing
{
sum+=sum1;
for(k=i;k<=j;k+=2)
{
a[s++]=a[k];
}
}
else
{
sum+=sum2;
for(k=(i+1);k<=j;k+=2)
{
a[s++]=a[k];
}
}
}
i=j;
}
i++;
}
if(pospre==1)
{
cout<<sum<<endl;
for(i=0;i<s;i++)
{
cout<<a[i]<<" ";
}
}
else{
k=a[0];
for(i=0;i<n;i++)
{
if(a[i]>k)
k=a[i];
}
cout<<k<<endl;
}
return 0;
}
3 5 3 6 3 2 5 6
| {6}
| {5}
| {2 + 6}
| {3 + 6}
| {6 + 2 + 6}
| {3 + 3 + 6}
| {5 + 6 + 2 + 6} = 19
| {3 + 6 + 2 + 6} = 17
* This starts from last to first
* For an element at i check only sum with i + 2, i + 3 (which ever is bigger)
* For a negative number remember the index of last biggest sum, and redirect to that element if queried
* If first number is non-positive it will have biggest sum (index to refer)
* If first number is positive and second is non-positive than first number has biggest sum
* If first and second both are positive biggest sum = max { first sequence sum, second sequence sum}
* Also keep a variable for lowest non-positive number found if first number is non-positive and has biggest sum still 0 or set nothing then print this lowest non-positive number
num =[2,3, -4, 1, 2, 5, 4, -3, 3, 5, 6, 2, 8, 8, 9, 9, -2, 5, 7, 7, 4,];
#This is a graph problem.
# sort the indices of the numbers and take only the ones > 0.
# pick each item for the summation for adding to the 'sumbag'. If the there is conflict
# due to prexisting adjacent recursively call sum with and wthout the conflicting item in the
# sumbag. In the end compare the sums and pick the sumbag with the largest sum.
def sum(num , sortidx, sumbag, skipbag, start, l):
tot1 = 0;
ary1 = [];
tot2 = 0;
ary2 = [];
for x in range(start, l):
if sortidx[x]-1 in sumbag and not sortidx[x]-1 in skipbag and not x-1 < 0:
ary1 = sumbag[:];
skp1 = skipbag[:];
ary1.remove(sortidx[x]-1);
skp1.append(sortidx[x]-1)
tot1, ary1 = sum(num, sortidx, ary1, skp1, x, l);
elif sortidx[x]+1 in sumbag and not sortidx[x]+1 in skipbag and not x+1 >= l:
ary2 = sumbag[:];
skp2 = skipbag[:];
ary2.remove(sortidx[x]+1);
skp2.append(sortidx[x]+1)
tot2, ary2 = sum(num, sortidx, ary2, skp2, x, l);
elif not sortidx[x] in skipbag:
sumbag.append(sortidx[x])
tot = 0;
for x in sumbag:
tot = tot + num[x];
if tot < tot1 :
tot = tot1;
sumbag = ary1;
if tot < tot2 :
tot = tot2;
sumbag = ary2;
return tot , sumbag;
#---------------------------------------------------------------------------
#sort the indices of the numbers and get only the ones greter than 0
sortedindex = [i[0] for i in reversed(sorted(enumerate(num), key=lambda x:x[1])) if num[i[0]] > 0];
sumb = [];
skipb = [];
l = len(sortedindex);
total , sumb = sum(num , sortedindex, sumb, skipb, 0, l);
print total ;
print sumb;
Here is the idea,
1. only interested on positive number,so negative numbers splits the whole array to multiple sub arrays which contains only positive number,
2. for each sub array, i.e. a(0), ..,a(n-1), use slide window (size=3) to get best pick. For current item, sum(j) = max( sum(j-2)+a(j), sum(j-3)+a(j)),
at the end, the result is max( sum(n-1), sum(n-2));
3. Now how to get contributed number? Reconsider the method in step 2, we should scan it in reverse order, i.e. n-1 to 0, then the result is either sum(0) or sum(1), say, R,
i=0;
while (R!=0) {
if (R==sum(i)) { print a(i); R = R-a(i); i--; }
i++;
}
space: O(N) to store sum for each positive number
time: O(N)
This is a DP solution to the problem
public class MaxSumMain {
public static int maxSum(int array[]) {
int sumArray[] = new int[array.length];
sumArray[0] = array[0];
sumArray[1] = array[1];
for(int i=2;i<array.length;i++) {
int tempArray[] = {sumArray[i-2],sumArray[i-1],array[i],sumArray[i-2]+array[i]};
sumArray[i] = max(tempArray);
}
return sumArray[sumArray.length-1];
}
/**
* @param tempArray
* @return
*/
private static int max(int[] tempArray) {
int maxElement = tempArray[0];
for(int i=1;i<tempArray.length ;i++){
if(tempArray[i] > maxElement)
maxElement = tempArray[i];
}
return maxElement;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int array[] = {-1,4,5,-2,-6,6};
//int array[] = {-1,-4,-5,-2,-6,-6};
System.out.println(maxSum(array));
}
}
Why don't e just split the Array wherever we find a -ve number and just use backtracking on the splited arrays to get their respective highest sum then combine the result.
Reason :1. we don't have to take -ve numbers in our ans anyways (omitting -ve number)
2. -ve numbers will give you freedom to chose any pattern in the next array since present array and next one will have always one element in between (-ve number we omitted) .
Why don't e just split the Array wherever we find a -ve number and just use backtracking on the splited arrays to get their respective highest sum then combine the result.
Reason :1. we don't have to take -ve numbers in our ans anyways (omitting -ve number)
2. -ve numbers will give you freedom to chose any pattern in the next array since present array and next one will have always one element in between (-ve number we omitted) .
public class CalcilateMaxSum {
public static void main(String[] args) {
int[] a= {-1,9,-5,-6};
System.out.println("Sum is::"+maxsum(a,0,0,0,Integer.MIN_VALUE));
}
public static int maxsum(int[] a,int sum,int k,int count,int min)
{
int sum1 =Integer.MIN_VALUE;
int sum2=0;
if(k>=a.length)
{
if(count==a.length)
return min;
return sum;
}
if(a[k]>0&&(k+1<a.length)&&a[k]<a[k+1])
{
sum1= maxsum(a,a[k+1],k+2,count,min);
System.out.print(k+1);
}
else if(a[k]>0)
{
sum1= maxsum(a, sum+a[k] , k+2,count,min) ;
System.out.print(k);
}
else
{
count = count+1;
if(min<a[k])
{min = a[k];}
sum2= maxsum(a,sum,k+1,count,min);
}
return Math.max(sum1, sum2);
}
}
public class CalcilateMaxSum {
public static void main(String[] args) {
int[] a= {-1,9,-5,-6};
System.out.println("Sum is::"+maxsum(a,0,0,0,Integer.MIN_VALUE));
}
public static int maxsum(int[] a,int sum,int k,int count,int min)
{
int sum1 =Integer.MIN_VALUE;
int sum2=0;
if(k>=a.length)
{
if(count==a.length)
return min;
return sum;
}
if(a[k]>0&&(k+1<a.length)&&a[k]<a[k+1])
{
sum1= maxsum(a,a[k+1],k+2,count,min);
System.out.print(k+1);
}
else if(a[k]>0)
{
sum1= maxsum(a, sum+a[k] , k+2,count,min) ;
System.out.print(k);
}
else
{
count = count+1;
if(min<a[k])
{min = a[k];}
sum2= maxsum(a,sum,k+1,count,min);
}
return Math.max(sum1, sum2);
}}
public static int MAX = -10;
// choose a reasonable value, should be lower than the min value in the given array
public static void main(String args[])
{
int[] arr = {-1, 4, 5, -2, -6, 6};
LinkedList<Integer> arrLst = new LinkedList<Integer>();
System.out.println(findMaxSum(arr, 0, arrLst));
for(Integer i: arrLst)
System.out.print(i+" ");
}
public static int findMaxSum(int[] arr, int index, LinkedList<Integer> arrLst)
{
if(index >=arr.length)
return MAX;
if(index == arr.length-1 || index == arr.length-2)
{
arrLst.add(arr[index]);
return arr[index];
}
LinkedList<Integer> arrLst2 = new LinkedList<Integer>();
LinkedList<Integer> arrLst3 = new LinkedList<Integer>();
int a = findMaxSum(arr, index+2, arrLst2);
int b = findMaxSum(arr, index+3, arrLst3);
int max =arr[index];
if(a > max)
{
modifyList(arrLst, arrLst2);
max = a;
}
if(b > max)
{
modifyList(arrLst, arrLst3);
//arrLst=(arrLst3);
max = b;
}
if(arr[index]+a > max)
{
modifyList(arrLst, arrLst2);
arrLst.add(arr[index]);
max = arr[index]+a;
}
if(arr[index]+b > max)
{
modifyList(arrLst, arrLst3);
arrLst.add(arr[index]);
max = arr[index]+b;
}
return max;
}
public static void modifyList(LinkedList<Integer> orig, LinkedList<Integer> newll)
{
orig.clear();
for(Integer i : newll)
orig.add(i);
}
can be achieved with a sliding window approach. Slide the window of size 3 by 1 every iteration and calculate the max and store it in the results array. Max calculator checks the last 2 max's for adjacents.
- vp August 06, 2014