Flipkart Interview Question
SDE1sCountry: India
Interview Type: In-Person
package com.dynamic;
public class MaximumRob {
public int getMaximum(int[] arr) {
int excl = 0;
int incl = arr[0];
int newExcl;
for (int i = 1; i < arr.length; i++) {
newExcl = (excl > incl) ? excl : incl;
incl = excl + arr[i];
excl = newExcl;
}
return (excl > incl) ? excl : incl;
}
public static void main(String args[]) {
int[] arr = { 10, 2, 3, 5, 7, 8 };
System.out.println(" Maximum sum is "
+ new MaximumRob().getMaximum(arr));
}
}
c# implementation.
via peak finding.
Running time 3*n.
O(n) complexity.
private static int GetViaPeakFinding( int[] arr ) {
int res = 0;
int prevPeak = -2;
for ( int i = 0; i < arr.Length; i++ ) {
if ( ( i == 0 || arr[ i ] > arr[ i - 1 ] ) && ( i == arr.Length - 1 || arr[ i ] > arr[ i + 1 ] ) ) {
res += arr[ i ];
var tmpSum1 = 0; var tmpSum2 = 0;
for ( int j = prevPeak + 2, k = i - 2; ( ( j < i - 1 ) && ( k > prevPeak + 1 ) ); j += 2, k -= 2 ) {
tmpSum1 += j < i - 1 ? arr[ j ] : 0;
tmpSum2 += k > prevPeak + 1 ? arr[ k ] : 0;
}
res += tmpSum1 > tmpSum2 ? tmpSum1 : tmpSum2;
prevPeak = i;
continue;
}
if ( i == arr.Length - 1 && arr[ i ] <= arr[ i - 1 ] ) {
for ( int j = prevPeak + 2; j < arr.Length; j += 2 ) {
res += arr[ j ];
}
}
}
return res;
}
Dynamic programming solution:
- AP May 31, 2015If I have 1,...i houses, Maximum sum that I can get is represented by recurrence relation:
OPT(i) = max(OPT(i-1), Pi + OPT(i - 2));
where Pi is amount you can get from house i.