Flipkart Interview Question
SDE-2sCountry: India
Interview Type: In-Person
very nyc solution
just 1 doubt ...ans = max (S[n], S[n-1], S[n-2]);
can u provide the test case where S[n-2] ll get selected
Thanks,
@kartikkhatri01: You are correct! S[n-2] < S[n] always!
Should be:
ans = max (S[n], S[n-1]);
What will be the solution for the question, if there were negative numbers also in the array? the current dp will not work.
Good question, Shrima!
For negative numbers, we need to change the DP formula. Obviously we can ignore the negative numbers, since they reduce the sum.
Define the optimization function:
S[k] = the maximum sum of the satisfied sub-sequence for the input array from A[0] to A[k];
Initial values:
S[0] = max (A[0], 0);
S[1] = max (A[1], S[0]);
Recursive formula:
For k>=2:
S[k] = S[k-1], if A[k] <=0; //i.e.: ignore A[k]
S[k] = max(A[k] + S[k-2], S[k-1]) , if A[k]>0 //i.e.: consider whether picking A[k] gives better sum.
From the definition of S[k], we can infer that:
S[u] >= S[u-1], for all u;
Thus, the recursive formula can be deduced to
S[k] = max( A[k] + S[k-2], S[k-1]);
The answer will be
ans = S[n];
To print out the sequence, we need to find out which position is picked in order to get the maximum sum. This can be done back-ward basing on the S[k] formula.
@ninhnnsoc
Formula you have given for DP would not work for input
9,2,8,1
because it will give 18,though its correct answer is 17
ex
s[0]=9
s[1]=2
s[2]=17
s[3]=1+17=18
correct DP formula should be
s(n)=s(n-2)+a(n),s(n-1)
where
//initilization
s[0]=9
s[1]=2
s[2]=17
s[3]=17
please correct me,if i am somewhere wrong.
suppose your init values are:
S[0] = a[0];
S[1] = a[1]; (?)
Let calculate S[] by your formula for this input: 9,2,1,8:
S[0] = 9;
S[1] = 2; (?)
S[2] = max(S[0] + 1, S[1]) = max(9 + 1, 2) = 10. Good!
S[3] = max(S[1] + 8, S[2]) = max(2 + 8,10) = 10, Not good!
Your formula is correct or not depends on how you define the meaning of S[k], and the initiated values.
(In my definition above, I force the subsequence must be ending at k, it's easier for logic and for printing out subsequence later).
You will correct if you define S[k] as the maximum sum of the satisfied subsequence of the array a[0] .. a[k], where the subsequence may or may not ending at k.
And the init value should be:
S[0] = a[0];
S[1] = max(a[0], a[1]); (!)
Recursive formula can be:
S[k] = max(S[k-1], S[k-2] + a[k]), for k>=2;
The answer will be:
ans = S[n];
However, it's a little bit more complicated for printing out the subsequence.
Can't we just make two arrays with alternative numbers and find max subset in both of them using kande's algo.
Whichever is max thats the answer.
For Maximum Subsequence, we have
int[] findSubsequence(int[] array, int start, int end) {
if(start > end || start < 0 || end >= array.length )
return {0};
if(start == end)
return {array[start]};
Below case is satisfied implicitly
// if(start >= 0 && end < array.length)
int max = Integer.MIN_VALUE;
int[] maxArray = {};
// Let k be in the range start and end
for(int k = start; k <= end; k++) {
int[] a1 = findSubsequence(array, start, k - 2);
int[] a = {array[k]};
int[] a2 = findSubsequence(array, k+ 2, end);
int[] A = Merge(a1, Merge(a, a2));
int sum = 0;
for(int i = 0; i < A.length; i++) {
sum = sum + A[i];
}
if(sum > max) {
maxArray = A;
max = sum;
}
}
return maxArray;
}
I didn't implement Merge algorithm, I hope it is simple and anyone would be able to write it.
Since the given array contains positive numbers we have make use of that information
int maxSequence(int[] array, int endingAt) {
if(endingAt < 2) {
return;
}
int maxIndex = 0;
if(endingAt - 2 == 0) {
maxIndex = 0;
}
else if(array[endingAt -2] >= array[endingAt - 3]) {
maxIndex = endingAt - 2;
}
else {
maxIndex = endingAt - 3;
}
System.out.print(new String(array[maxIndex]) + " ");
return (array[maxIndex] + maxSequence(array, maxIndex));
}
// Inside main method
public static void main(String[] args) {
int array[] = {......................................}
int endingAt = array.length - 1;
if(array.length < 2)
System.out.println("No such sequence Possible");
if(array[endingAt] < array[endingAt - 1]) {
endingAt = endingAt - 1;
}
System.out.println(maxSequence(array, endingAt));
}
yeah, simple recursive solution.
S(k) = max(S(k-2) + a[k], S(k-1).
public int sum(int[] input) {
return sum(0, input)
}
private int sum(int index, int[] input) {
if (index >= input.length) return 0;
return Math.max(
sum(index+1, input),
sum(index+2, input) +input[index]
);
}
If you bother about printing subsequeunce also, you can pass a list and add input[index] to list if sum(index+2, input) is greater.
Only problem with the recursive solution is you would be computing S(k) over and over again. You can get rid of this by memorization.
store S(k) in maxIndex when you compute S(k). So next time you can get S(k) from it. You have to initialize maxIndex with all -1.
public int sum(int index, int[] input, int[] maxIndex) {
if (index >= input.length) return 0;
if (maxIndex[index] != -1) {
return maxIndex[index];
}
int result = Math.max(
sum(index+1, input, maxIndex),
sum(index+2, input, maxIndex) +input[index]
);
maxIndex[index] = result;
return result;
}
Python
def maxSub(arr):
start = 0
top = (0,0)
for x in range(len(arr)):
if x == len(arr)-1 or arr[x] == arr[x+1]:
if sum(arr[start:x+1])>sum(arr[top[0]:top[1]+1]):
top = (start, x)
start = x+1
print sum(arr[top[0]:top[1]+1]), arr[top[0]:top[1]+1]
Since the array contains only positive integers, there's no need to break out recursion (if there were negative numbers, it's possible that a shorter subsequence of a larger non-repeating sequence could have a higher sum, which recursion would help catch). Just iterate through the array finding the subsequences that don't have any repeated numbers and record the highest sum. Basically a modified linear search.
C# code
public void GetMaxSub( int[] numbers )
{
int[] sum = new int[numbers.Length];
int[] prev = new int[numbers.Length];
for( int i = 0; i < numbers.Length; i++ )
{
int maxSum = 0;
int bestPrev = -1;
for( int j = 0; j < i - 1; j++ )
{
if( sum[j] > maxSum )
{
maxSum = sum[j];
bestPrev = j;
}
}
sum[i] = maxSum + numbers[i];
prev[i] = bestPrev;
}
int maxPos = 0;
int prevMax = 0;
for( int i = 0; i < sum.Length; i++ )
{
if( sum[i] > prevMax )
{
prevMax = sum[i];
maxPos = i;
}
}
Console.WriteLine( prevMax );
while( maxPos >= 0 )
{
Console.Write( numbers[maxPos] + " ");
maxPos = prev[maxPos];
}
}
I have a array A[] = {1,2,5,10,11,3,9}
n is the length of A; n = A.length
with an exemption n >=3
A[k]= 5
A[k-1] = 2
A[k-2] = 1
previous = A[k-2]; 2
max(A[k-1],A[k-2]) = 2
max(A[k-1],A[k-2]) + A[k] on a condition max(A[k-1],A[k-2]) != previous
if(max(A[k-1],A[k-2]) != previous)
{
sum[counter] = max(A[k-1],A[k-2]) + A[k]
counter++;
}else
{
sum[counter] = A[k]
counter++;
}
previous = A[k-2]
After this iterate over sum array and find the maximum number.
int MAX(int a, int b)
{
return a>b?a:b;
}
int GetMax(int input[], int size)
{
int sumL1 = input[0];
int sumL2 = input[1];
int max = 0;
for(int i = 2; i<size; i++)
{
max = MAX(sumL2, input[i]+sumL1);
sumL1 = sumL2;
sumL2 = max;
}
return max;
}
int main()
{
cout << "Hello World" << endl;
int input[]={1,2,3,4,15,6};
cout<<GetMax(input, 6);
return 0;
}
int MAX(int a, int b)
{
return a>b?a:b;
}
int GetMax(int input[], int size)
{
int sumL1 = input[0];
int sumL2 = input[1];
int max = 0;
for(int i = 2; i<size; i++)
{
max = MAX(sumL2, input[i]+sumL1);
sumL1 = sumL2;
sumL2 = max;
}
return max;
}
int main()
{
cout << "Hello World" << endl;
int input[]={1,2,3,4,15,6};
cout<<GetMax(input, 6);
return 0;
}
class Program
{
static void Main(string[] args)
{
Console.WriteLine(FindMaxSequence(new int[] { 8, 1, 1, 3, 1 }));
Console.WriteLine(FindMaxSequence(new int[] { 2,1,5,3,1,7,9,8,2,8 }));
Console.WriteLine(FindMaxSequence(new int[] { 9,2,8,1 }));
}
/// <summary>
/// Contributed by Pramod Chandoria
/// We will devide the problem and solve it recursively
/// </summary>
/// <param name="sequence"></param>
/// <param name="startIndex"></param>
/// <returns></returns>
static int FindMaxSequence(int[] sequence, int startIndex = 0)
{
int elements = sequence.Length - startIndex;
if (elements <=0)
{
return 0;
}
if (elements == 1)
{
return sequence[startIndex];
}
int max1 = FindMaxSequence(sequence, startIndex + 1);
int max2 = sequence[startIndex] + FindMaxSequence(sequence, startIndex + 2);
return Math.Max(max1, max2);
}
}
And This is optimized solution
class Program
{
static void Main(string[] args)
{
Console.WriteLine(FindMaxSequence(new int[] { 2, 1, 5, 3, 1, 7, 9, 8, 2, 8 }));
Console.WriteLine("Count=" + called + " for n=10");
called = 0;
Console.WriteLine(FindMaxSequence(new int[] { 8, 1, 1, 3, 1 }));
Console.WriteLine("Count=" + called + " for n=5");
called = 0;
Console.WriteLine(FindMaxSequence(new int[] { 9, 2, 8, 1 }));
Console.WriteLine("Count=" + called + " for n=4");
called = 0;
var sequence = new int[]
{
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 5, 3, 3, 4, 5, 6, 7, 8, 9, 6, 5, 3, 2, 1, 4, 4, 100,
12, 1, 34, 45
};
Console.WriteLine(FindMaxSequence(sequence));
Console.WriteLine("Count=" + called + " for n=" + sequence.Length);
called = 0;
}
static int FindMaxSequence(int[] sequence)
{
int secondSum = 0;
int firstSum = 0;
FindMaxSequence(sequence, 0, out firstSum, out secondSum);
return Math.Max(firstSum, secondSum);
}
static int called = 0;
/// <summary>
/// Contributed by Pramod Chandoria
/// We will devide the problem and solve it recursively
/// </summary>
/// <param name="sequence"></param>
/// <param name="startIndex"></param>
/// <param name="firstSum"></param>
/// <param name="secondSum"></param>
static void FindMaxSequence(int[] sequence, int startIndex, out int firstSum, out int secondSum)
{
called++;
int elements = sequence.Length - startIndex;
if (elements <=0)
{
secondSum = 0;
firstSum = 0;
return;
}
if (elements == 1)
{
secondSum = 0;
firstSum = sequence[startIndex];
return;
}
else if (elements == 2)
{
secondSum = sequence[startIndex + 1];
firstSum = sequence[startIndex];
return;
}
FindMaxSequence(sequence, startIndex + 2, out firstSum, out secondSum);
firstSum = sequence[startIndex] + Math.Max(firstSum, secondSum);
secondSum = sequence[startIndex + 1] + secondSum;
return;
}
solution in Time complexity O(n) and space compexity O(1)
def maxSeq(lst):
maxSum = 0
sum = lst[0];
i = 0
j = 1
l = len(lst)
start = 0
end = 0
while True:
if j == l:
break;
if lst[j - 1] == lst[j]:
i = j
j += 1
sum = lst[i]
else:
sum += lst[j]
j += 1
if sum > maxSum:
maxSum = sum
start = i
end = j
print maxSum, seq[start:end]
seq = [1,2,10,11,3,4,4,15,15,6]
maxSeq(seq)
DP O(n) solution:
Let S[k] = maximum sum of the subsequence that: (1) finishes at position k, and (2) satisfies the constraint.
Init values:
Recursive formula:
Note: we don't need to care about S[k-4], since if it is in optimal solution, it must be included in S[k-2] already.
The answer is
DP table can be computed in O(n) time.
To print the subsequence, we need to record the position where the maximum is achieved, using an array Prev[], like this:
- ninhnnsoc April 27, 2014