makemytrip Interview Question
Senior Software Development EngineersCountry: India
A nice and simple one, just need to consider all the edge cases. for eg. what if all elements are negative/zero. A single traverse would be enough while storing the start and ending index of continuous positive elements and their current sum.
My c++ implementation is :
void printSubset(int arr[],int n)
{
int i,sum=INT_MIN,current=0,start=0,end=0,s,e;
for(i=0;i<n;)
{
s=i;
while(i<n && arr[i]>0)
{
current+=arr[i];
i++;
}
e=i-1;
if(sum<current) // update indices if current sum exceeds the total one
{
sum=current;
start=s;
end=e;
current=0;
}
i++;
while(i<n && arr[i]<=0) // find the next positive number
i++;
}
if(end==-1) cout<<"All are negative or zero";
else cout<<start<<" "<<end;
}
Final Solution -
int[][] subseqSum = new int[arr.length][2];
subseqSum[0][0] = arr[0];
subseqSum[0][1] = 0;
int maxSum = arr[0];
int maxSumEndPos = 0;
for(int i = 1; i < arr.length; i++){
if(arr[i] < 0) {
subseqSum[i][0] = arr[i];
subseqSum[i][1] = 0;
}
else{
if(subseqSum[i-1][0] >= 0){
subseqSum[i][0] = subseqSum[i-1][0] + arr[i];
subseqSum[i][1] = subseqSum[i-1][1] + 1;
}else{
subseqSum[i][0] = arr[i];
subseqSum[i][1] = 1;
}
if(maxSum < subseqSum[i][0]){
maxSum = subseqSum[i][0];
maxSumEndPos = i;
}
}
}
return Arrays.copyOfRange(arr, maxSumEndPos - subseqSum[maxSumEndPos][1], maxSumEndPos+1);
Python solution, probably doesn't cover all edge conditions though.
Simple idea: find the positive subarrays, and compare them..
def cont_pos_subarray(idx,arr):
subarray = []
last_num = arr[idx]
if (last_num > 0):
subarray.append(last_num)
end_index = idx
for i in range(idx+1,len(arr)):
if arr[i] > last_num:
last_num = arr[i]
subarray.append(last_num)
else:
end_index = i
break
if i == len(arr) -1:
end_index = i
return (subarray, end_index)
def subarrays(arr):
i = 0
arrays = []
while (i < (len(arr)-1)):
subarray, end_index = cont_pos_subarray(i,arr)
print subarray
arrays.append(subarray)
i = end_index
return arrays
def highest_sum_subarray(array):
max_arr = []
for arr in subarrays(array):
if (sum(arr)> sum(max_arr)):
max_arr = arr
return max_arr
if __name__ == "__main__":
arr = [1,2,5,-7,2,5]
print(cont_pos_subarray(0, arr))
print(cont_pos_subarray(3, arr))
print(subarrays(arr))
print(highest_sum_subarray(arr))
DP Solution... Store the max sum and no. elements included in the sum in a two dimensional array.
int[][] subseqSum = new int[arr.length][2];
subseqSum[0][0] = arr[0];
subseqSum[0][1] = 0;
for(int i = 1; i < arr.length; i++){
if(arr[i] < 0) {
subseqSum[i][0] = arr[i];
subseqSum[i][1] = 0;
}
else{
if(subseqSum[i-1][0] >= 0){
subseqSum[i][0] = subseqSum[i-1][0] + arr[i];
subseqSum[i][1] = subseqSum[i-1][1] + 1;
}else{
subseqSum[i][0] = arr[i];
subseqSum[i][1] = 1;
}
}
}
Final Solution
int[][] subseqSum = new int[arr.length][2];
subseqSum[0][0] = arr[0];
subseqSum[0][1] = 0;
int maxSum = arr[0];
int maxSumEndPos = 0;
for(int i = 1; i < arr.length; i++){
if(arr[i] < 0) {
subseqSum[i][0] = arr[i];
subseqSum[i][1] = 0;
}
else{
if(subseqSum[i-1][0] >= 0){
subseqSum[i][0] = subseqSum[i-1][0] + arr[i];
subseqSum[i][1] = subseqSum[i-1][1] + 1;
}else{
subseqSum[i][0] = arr[i];
subseqSum[i][1] = 1;
}
if(maxSum < subseqSum[i][0]){
maxSum = subseqSum[i][0];
maxSumEndPos = i;
}
}
}
return Arrays.copyOfRange(arr, maxSumEndPos - subseqSum[maxSumEndPos][1], maxSumEndPos+1);
public static void largerSubArray(int[] arr){
int firstSum = 0; // sum of first subArray
int nextSum = 0; // sum of next subArray
int i = 0;
while(arr[i] < 0 && i < arr.length){ // edge case --> if index 0 has a -ve num
i++;
}
int firstStart = i; // start index of first subArray
while (arr[i] >= 0 && i < arr.length) {
firstSum += arr[i];
i++;
}
int firstEnd = i;
i++;
int nextStart = i; // // start index of next subArray
while(i < arr.length) {
nextSum += arr[i];
i++;
}
int nextEnd = i;
if (firstSum > nextSum){
int[] firstSubset = Arrays.copyOfRange(arr, firstStart, firstEnd);
System.out.println(Arrays.toString(firstSubset));
} else {
int[] nextSubset = Arrays.copyOfRange(arr, nextStart, nextEnd);
System.out.println(Arrays.toString(nextSubset));
}
}
public static int[] findLargestSum(int[] arr){
int cSum = 0, maxSum = 0;
int startI = 0;
int endI = 0;
int maxStart =0, maxEnd=0;
for (int i = 0; i < arr.length; i++){
if (cSum == 0){
startI = i;
}
if (arr[i] >= 0){
cSum += arr[i];
endI = i;
if (cSum > maxSum){
maxStart = startI;
maxSum = cSum;
maxEnd = endI;
}
}
else {
cSum = 0;
}
}
if (endI == 0){ return new int[0];}
return Arrays.copyOfRange(arr, maxStart, maxEnd+1);
}
private int[] findLargestSubset(int[] arr){
int sum = 0, maxSum =0, startIdx = 0, endIdx = 0, startI = 0;
boolean restart = true;
for (int i = 0; i < arr.length; i++) {
if(sum == 0){
startI = i;
}
sum += arr[i];
if(sum > maxSum){
maxSum = sum;
startIdx = startI;
endIdx = i;
restart = true;
} else if(restart) {
sum = 0;
restart = false;
}
}
return Arrays.copyOfRange(arr, startIdx, endIdx+1);
}
The idea is to find all the subsets of array and if the sum is greater return the subset. Only drawback is it uses extra space for storing two arraylists.
public static List<Integer> largestSubset(int[] ar) {
List<Integer> temp = null;
int n = ar.length;
int max = 0;
List<Integer> templist;
for (int i = 1; i < n; i++) {
int j = 0;
templist = new ArrayList<Integer>();
while (j < n) {
while (templist.size() <= i) {
templist.add(ar[j]);
j++;
}
int tempSum = arraySum(templist);
if (max < tempSum) {
max = tempSum;
temp = new ArrayList<Integer>(templist);
}
templist.remove(0);
}
}
return temp;
}
public static int arraySum(List<Integer> ar) {
int sum = 0;
for (int temp : ar)
sum += temp;
return sum;
}
Here is dynamic programming recursive formula...
Lets take an two dimensional array R[n][n] to store the subsets sums.
Lets A is the given array.
sum_all(A[i...j]) = returns sum of all elements of A from i to j.
max_store(...) = return max sum and reserve the indexes of mx sum within the frame of (i, j).
0 < i < j < n
if(i > j) {
return 0;
} else if (i == j) {
return (R[i][j] = A[i]);
} else {
R[i][j] = max_store(S(i+1, j-1), S(i, j-1), S(i+1, j), sum_all(i, j));
return R[i][j];
}
Considering all the boundary cases
l=[1,2, 8, -7, 2,12,-7,13]
currsum=currst=currend=maxsum=prevst=prevend=0
for i in range(0,len(l)):
if l[i]>0:
if currsum==0:
currst=i
currend=i
else:
currend=i
currsum+=l[i]
else:
if maxsum<currsum:
maxsum=currsum
prevst=currst
prevend=currend
currsum=0
if maxsum<currsum:
maxsum=currsum
prevst=currst
prevend=currend
print maxsum,"=>",l[prevst:prevend+1]
output=>>
14 => [2, 12]
public static Integer[] continuousPositive(Integer[] array) {
Integer maxSum = 0;
Integer startPoint = 0;
Integer endPoint = 0;
for(int i= 0; i<array.length; i++) {
boolean foundNegative = false;
int j = i;
Integer sum = 0;
while(i<array.length && !foundNegative) {
if(array[i] > 0) {
sum += array[i];
++i;
} else {
if(sum > maxSum) {
startPoint = j;
endPoint = i;
maxSum = sum;
}
++i;
foundNegative = true;
}
}
}
return Arrays.copyOfRange(array,startPoint,endPoint);
}
Since we're looking for a subarray with positive numbers we can easily do this in linear time.
This should cover all the border cases:
1. If the number is negative, reset the counters
2. If the number is positive, update the current counter and if need be update the max.
pair<int,int> maxContinuousSubarray(vector<int> v){
if(v.size()==0)
return make_pair(-1,-1);
int maxSoFar = 0, maxCur = 0;
int maxStart = -1, maxEnd = -1;
int maxStartCurrent = 0;
for(int i = 0; i < v.size(); i++){
if(v[i] < 0){
maxStartCurrent = i+1;
maxCur = 0;
} else {
maxCur+=v[i];
if(maxCur > maxSoFar){
maxStart = maxStartCurrent;
maxEnd = i;
maxSoFar = maxCur;
}
}
}
return make_pair(maxStart,maxEnd);
}
#include<iostream>
#include<vector>
using namespace std;
int main() {
vector<int> v ;
int n=0;
cout << " Enter total number of integers : " << endl;
cin >> n;
cout << " Enter " << n << " positive and negative numbers : " ;
int temp_sum = 0, max_sum =0, start_index = -1, end_index = -1, temp_start_index = 0;
for(int i=0; i<n; i++) {
int num = 0;
cout << endl << i << "th number : ";
cin >> num;
v.push_back(num);
if(num >=0) {
temp_sum = temp_sum + num;
if(max_sum < temp_sum) {
max_sum = temp_sum;
end_index = i;
start_index = temp_start_index;
}
}
else {
temp_sum = 0;
temp_start_index = i + 1;
}
}
cout << " Subarray with max sum : " << endl;
for(int i = start_index; i <= end_index; i++) {
cout << v[i] << " ";
}
return 0;
}
Code looks a bit tough for understanding and massive, but the sense is simple: we keep counters for sum (current and maximum) and indices of range (current and maximum), As maximum sum exceeds current one - we remember new indices as maxumum ones. The special case is tail - after iteration we must check the last element.
- alisovenko October 04, 2014