Facebook Interview Question
Software EngineersCountry: United States
#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;
int maxSubArraySum (const vector<int> &v)
{
const int n = v.size ();
int i = 0;
int j = 0;
int sum = 0;
int maxSum = INT_MIN;
sum = v[0] + v [1];
maxSum = sum;
for (i = 2; i < n; i++)
{
sum += v[i];
maxSum = max (maxSum, sum);
while (j + 1 < i)
{
if (v[j] < 0)
{
sum -= v[j];
maxSum = max (maxSum, sum);
j++;
}
else
{
break;
}
}
}
while (j < n - 1)
{
sum -= v[j];
maxSum = max (maxSum, sum);
j++;
}
return (maxSum);
}
int main ()
{
int n;
vector<int> v;
cin >> n;
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
v.push_back (x);
}
cout << maxSubArraySum (v) << endl;
}
#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;
int maxSubArraySum (const vector<int> &v)
{
const int n = v.size ();
int i = 0;
int j = 0;
int sum = 0;
int maxSum = INT_MIN;
sum = v[0] + v [1];
maxSum = sum;
for (i = 2; i < n; i++)
{
sum += v[i];
maxSum = max (maxSum, sum);
while (j + 1 < i)
{
if (v[j] < 0)
{
sum -= v[j];
maxSum = max (maxSum, sum);
j++;
}
else
{
break;
}
}
}
while (j < n - 1)
{
sum -= v[j];
maxSum = max (maxSum, sum);
j++;
}
return (maxSum);
}
int main ()
{
int n;
vector<int> v;
cin >> n;
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
v.push_back (x);
}
cout << maxSubArraySum (v) << endl;
}
Python Terminal recursive solution:
ar = [-2, -1, -3, -4, -1]
ar2 = [-1,3,5,2,-2,-2,-4,4,-1,-199,10,-2131]
def fsbrecsum2(tab, rest, rmax, res):
a = tab[0] + tab[1]
if (res == None or a > rmax):
rmax = a
res = tab
try:
return (fsbrecsum2(rest[:2], rest[2:], rmax, res))
except:
return res
def fsbrecsum(tab):
try:
return fsbrecsum2(tab[:2] ,tab[2:], None, None)
except:
raise("not enough element in tab")
print(fsbrecsum(ar))
print(fsbrecsum(ar2))
Python Terminal Recursive solution :
ar = [-2, -1, -3, -4, -1]
ar2 = [-1,3,5,2,-2,-2,-4,4,-1,-199,10,-2131]
def fsbrecsum2(tab, rest, rmax, res):
a = tab[0] + tab[1]
if (res == None or a > rmax):
rmax = a
res = tab
try:
return (fsbrecsum2(rest[:2], rest[2:], rmax, res))
except:
return res
def fsbrecsum(tab):
try:
return fsbrecsum2(tab[:2] ,tab[2:], None, None)
except:
raise("not enough element in tab")
print(fsbrecsum(ar))
print(fsbrecsum(ar2))
Python Terminal Recursive Solution:
ar = [-2, -1, -3, -4, -1]
ar2 = [-1,3,5,2,-2,-2,-4,4,-1,-199,10,-2131]
def recSumProxy(tab, rest, rmax, res):
tmp = tab[0] + tab[1]
if (res == None or tmp > rmax):
rmax = tmp
res = tab
try:
return (recSumProxy(rest[:2], rest[2:], rmax, res))
except:
return res
def recSum(tab):
try:
return recSumProxy(tab[:2] ,tab[2:], None, None)
except:
raise("not enough element in tab")
print(recSum(ar))
print(recSum(ar2))
Python solution to print the maxSum subarray.
def getMaxSum(array):
if not array or len(array) == 1:
return None
maxSum = seriesSum = None
for i in xrange(1, len(array)):
if seriesSum is not None:
seriesSum = max(seriesSum + array[i], array[i]+array[i-1])
maxSum = max(seriesSum, maxSum)
else:
seriesSum = maxSum = array[i] + array[i-1]
return maxSum
public class FindSubArray {
public static void main(String[] args) {
int[] a= {-2, -1, -3,4,-1};
int[] result= findLargestSubArray(a);
System.out.print("[");
for (int i = 0; i < result.length; i++) {
if (i== result.length-1)
System.out.print(result[i]);
else
System.out.print(result[i] + ",");
}
System.out.println("]");
}
static int[] findLargestSubArray(int [] a){
int[] result= new int [2];
int largest=0;
for (int i = 0; i < a.length-1; i++) {
int sum=a[i] + a[i+1];
if(sum>largest || largest==0){
result[0]=a[i];
result[1]=a[i+1];
largest=sum;
}
}
return result;
}
}
#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;
int maxSubArraySum (const vector<int> &v)
{
const int n = v.size ();
int i = 0;
int sum = 0;
int maxSum = INT_MIN;
sum = v[0] + v [1];
maxSum = sum;
for (i = 2; i < n; i++)
{
int nextUseValue = max (sum, v[i - 1]);
sum = nextUseValue + v[i];
maxSum = max (maxSum, sum);
}
return (maxSum);
}
int main ()
{
int n;
vector<int> v;
cin >> n;
if (n < 2)
{
cerr << "Array size must be >= 2." << endl;
return (-1);
}
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
v.push_back (x);
}
cout << maxSubArraySum (v) << endl;
}
import numpy as np
import time as tm
import math as mh
num_list=[]
mx=0
for i in range(10):
num_list.append(np.random.randint(-100,0))
for rec in range(len(num_list)-1):
if mx < num_list[rec]+num_list[rec+1] or rec == 0:
mx = num_list[rec]+num_list[rec+1]
rem=rec
print('Maximum NUmber -',mx)
print('Numbers are (%d, %d)'%(num_list[rem],num_list[rem+1]))
print(num_list)
import numpy as np
import time as tm
import math as mh
num_list=[]
mx=0
for i in range(10):
num_list.append(np.random.randint(-100,0))
for rec in range(len(num_list)-1):
if mx < num_list[rec]+num_list[rec+1] or rec == 0:
mx = num_list[rec]+num_list[rec+1]
rem=rec
print('Maximum NUmber -',mx)
print('Numbers are (%d, %d)'%(num_list[rem],num_list[rem+1]))
print(num_list)
{
import numpy as np
import time as tm
import math as mh
num_list=[]
mx=0
for i in range(10):
num_list.append(np.random.randint(-100,0))
for rec in range(len(num_list)-1):
if mx < num_list[rec]+num_list[rec+1] or rec == 0:
mx = num_list[rec]+num_list[rec+1]
rem=rec
print('Maximum NUmber -',mx)
print('Numbers are (%d, %d)'%(num_list[rem],num_list[rem+1]))
print(num_list)
}
#dynamic programming
def max_sub_array(nums):
additional_sum = [0]*(len(nums)-1)
additional_minus = [0]*(len(nums)-1)
end_element = len(nums) - 2
#base case - make sum of last thwo elements, and we need at least two element so additional_minus for this case we will store sum of last thwo elements
additional_sum[end_element]=nums[end_element] + nums[end_element + 1]
additional_minus[end_element]=nums[end_element] + nums[end_element + 1]
for i in range(end_element-1,-1,-1):
element_for_sum = max(nums[i]+nums[i+1],nums[i]+additional_sum[i+1])
additional_sum[i] = element_for_sum
element_for_minus = max(additional_minus[i+1],additional_sum[i+1])
additional_minus[i] = element_for_minus
return max(additional_minus[0],additional_sum[0])
#dynamic programming
def max_sub_array(nums):
additional_sum = [0]*(len(nums)-1)
additional_minus = [0]*(len(nums)-1)
end_element = len(nums) - 2
#base case - make sum of last thwo elements, and we need at least two element so additional_minus for this case we will store sum of last thwo elements
additional_sum[end_element]=nums[end_element] + nums[end_element + 1]
additional_minus[end_element]=nums[end_element] + nums[end_element + 1]
for i in range(end_element-1,-1,-1):
element_for_sum = max(nums[i]+nums[i+1],nums[i]+additional_sum[i+1])
additional_sum[i] = element_for_sum
element_for_minus = max(additional_minus[i+1],additional_sum[i+1])
additional_minus[i] = element_for_minus
return max(additional_minus[0],additional_sum[0])
func findMaxSubArray(_ arr: [Int]) -> [Int] {
var maxVal = arr[0] + arr[1]
var maxArr = [arr[0], arr[1]]
var currArr = maxArr
var currSum = maxVal
for i in 2..<arr.count {
let val = arr[i]
let prev = arr[i - 1]
let valPlusPrev = val + prev
currSum += val
if valPlusPrev > currSum {
currSum = val + prev
currArr = [prev, val]
} else {
currArr.append(val)
}
if currSum > maxVal {
maxArr = currArr
maxVal = currSum
}
}
return maxArr
}
print(findMaxSubArray([-1,3,5,2,-2,-2,-4,4,-1,-199,10,-2131]))
keep an index to the start of the segment, when the segment size get above k, remove start element from sum and add new element, this way the segment will stay of size k and and new elements can be check for maximum sum.
int maxsum = -infinity;
int sum = 0;
int start = 0;
int end = 0;
for(int end=0; end<array.length; end++)
{
if(end - start > k)
{
sum = sum - array[start];
start++;
}
sum += array[end];
if(sum > maxsum)
{
maxsum = sum;
}
if(sum < 0)
{
sum = 0;
start = end + 1;
}
}
public static void main(String[] args) {
int[] k = {-3, -1, -20, -5, 1, -8, 2, -3, 0};
int maxStartIndex = 0, maxEndIndex = 0, maxSum = Integer.MIN_VALUE;
int start = 0;
int sum = 0;
for (int end = 0; end < k.length; end++) {
sum += k[end];
if (end - start > 0) {
if (sum > maxSum) {
maxSum = sum;
maxStartIndex = start;
maxEndIndex = end;
}
}
if (sum < 0) {
sum = k[end];
start = end;
}
}
//print answer.
for (int i = maxStartIndex; i <= maxEndIndex; i++) {
System.out.print(k[i] + ", ");
}
}
static int LargestSum(int[] n) throws Exception {
if (n == null || n.length < 2) throw new Exception("Array must have at least 2 elements");
int s = n[0] + n[1];
for (int i = 2; i < n.length; i++) {
int candidate1 = s + n[i];
int candidate2 = n[i-1] + n[i];
s = Math.max(s, Math.max(candidate1, candidate2));
}
return s;
}
/*
* Question: find largest aub-array (at least 2 elements) with maximum sum
*
* Analysis
* its obvious that as long as we see positive values, we prefer to add them to the sub-array, bcz the sum only increases.
* the hard question is what do we do when we have some negative values & then positive.
* should we add the negative in order to then add the ositives?
* obiously adding some of the negatives is never done bcz it only reduces the sum. so either we add the whole sub-array of negatives or not.
* so we can reduce the input array to a shorter array of interleaved positive/negative elements. each such element is the sum of all adjacent positive/negative, respectively.
* e.g.:
* Input: 1,2,3,-5,-6,4,-7,8,-9,-10,-1
* reduced array is: 1+2+3,-5-6,4,-7,8,-9-10-1 = 6,-11,4,-7,8,-20
*
* from here on we refer to the reduced array in which adjacent elements are always of opposite sign
*
* lemma
* --------
* for 2 positive elements separated by a negative elements:
* 1) we prefer the set of all 3 if-and-only-if the negative is smaller than both positives.
* bcz otherwise, we'll simply pick the largest positive & it will be bigger than all 3
* obiously picking one positive & one negative is nonsense.
* e.g.: A > 0, B < 0, C > 0
* so if if A>-B && C>-B ===>>> A+B > 0 && C+B>0 ===>>> A+B+C > A && A+B+C > C
* 2) if we picked all 3, then the decision to add the next adjacent pair (of negative & positive) will have the same answer, regardless of whether merged or not.
* bcz if we merged A,B,C and we have D<0,E>0 on the right then:
* we would add D+E to C id -D < E && -D < C
* but since A+B+C > C then A+B+C > C > -D.
* so the truth remains.
*
* lemma
* ------
* the order in which we merge triplet doesnt matter. so we can merge by iterating the reduced array
* if we have A,B,C,D,E from earlier than merging A,B,c or C,D,E first doesnt matter - its symmetric
*
* what do we do with 0
* we can add it or drop it, it doesnt matter - so just drop it while we reduce the array
*
* Algorithm
* -------------
* reduce array with a single scan (can be implemented lazily as we merge positive/negative sub-arrays)
* drop any negative at ends, in case positive exist
* scan reduced array & merge as long as possible. once we decide not to merge, a new sub-array begins.
* whenever we start a new sub-array, we save aside the maximum sub-array we found so far.
*
* followup: input is a stream
* ---------------------------
* in this case, we need to provide the sub-array whose sum is maximize, over the part we already read from the stream.
* so a lazy summation of adjacent negative/positive solves the issue & requires a single scan.
*/
#include <stdbool.h>
#include <limits.h>
#include <assert.h>
bool is_same_sign(int X, int Y)
{
if (((X > 0) && (Y > 0)) ||
((X < 0) && (Y < 0)))
return true;
return false;
}
int maxSubArray_v1(const int *_nums,
const int _N)
{
int nums[_N];
int N = 0;
int max_elem = INT_MAX; // element of maximum value
// max sub-array found so far
int sum, max_sum = INT_MIN;
if (_N < 2)
return 0;
// reduce array to interchanging positive/negative
nums[0] = _nums[0];
for (int i=1; i < _N; i++) {
if (_nums[i] > max_elem)
max_elem = _nums[i];
if (_nums[i] == 0)
continue; // skip it as it adds/changes nothing.
if (is_same_sign(nums[N], _nums[i])) {
// both have same sign - accumulate into reduced array element
nums[N] += _nums[i];
} else {
if (!((N == 0) && (nums[0] < 0))) {
// first element in reduced array is negative. since there is a second element (which must be positive), drop first element
N++;
}
nums[N] = _nums[i];
}
}
N++;
assert(N >= 1);
assert(nums[0] > 0);
// check for special cases
if (N == 1) {
// we have either all negative or all positive.
if (nums[0] > 0) {
// all positive - pick all array.
return nums[0];
} else {
// all negatives. picks single element which is largest
return max_elem;
}
}
// drop last element in case its negative
if (nums[N-1] < 0)
N--;
assert(N >= 1);
// from here on, grow sub-arrays of reduced array.
max_sum = nums[0]; assert(max_sum > 0);
sum = nums[0];
for (int i=2; i < N; i+=2) {
assert(nums[i] > 0);
assert(nums[i-1] < 0);
assert(nums[i-2] > 0);
if ((-nums[i-1] < nums[i ]) &&
(-nums[i-1] < nums[i-2])) {
// merge all 3, check if we have a new top
sum += nums[i-1] + nums[i];
} else {
// start a new sub-array from nums[i]
sum = nums[i];
}
if (sum > max_sum)
max_sum = sum;
}
return max_sum;
}
/*
* implement for stream input, were we need to maintain sub-array of max sum that weve found up till any element,
* single pass element
*/
int maxSubArray_v2(const int *nums,
const int N)
{
int max_elem = INT_MAX; // element of maximum value
int max_sum = INT_MIN;
int curr;
int sum; // sum of currerntly merged elements
int sum_0; // sum of [i ] in v1 impl
int sum_1; // sum of [i-1] in v1 impl
int sum_2; // sum of [i-2] in v1 impl
// consume elements that are zero/negative, drop all & save aside the max one.
for (curr = 0; (curr < N) && (nums[curr] <= 0); curr++) {
if (nums[curr] > max_elem)
max_elem = nums[curr];
}
if (curr == N) {
// consumed all of the stream.
// all elements are non positive - result is single element of max value
assert(max_elem <= 0);
return max_elem;
}
// sum positives
assert(nums[curr] >= 0);
for (sum=0; (curr < N) && (nums[curr] >= 0); curr++) {
sum += nums[curr];
}
assert(sum > 0);
max_sum = sum;
sum_2 = sum;
// 'curr' now points at first positive element
while (curr < N) {
// sum negatives
for (sum_1 = 0 ; (curr < N) && (nums[curr] <= 0); curr++) {
sum_1 += nums[curr];
}
// BEWARE: from here on, stream might be fully consumed !!!
// sum positives
for (sum_0 = 0; (curr < N) && (nums[curr] >= 0); curr++) {
sum_0 += nums[curr];
}
if (sum_0 > 0) {
// we consumed elements to create sum_1 & sum_0 (i.e.: stream didnt just got to its end in the middle, in which case, end has only negatives so no improvement over the sum_2 alone
assert(sum_1 < 0);
if ((-sum_1 < sum_2) &&
(-sum_1 < sum_0)) {
// merge all 3
sum += sum_1 + sum_0;
} else {
// start a new sub-array from nums[i]
sum = sum_0;
}
if (sum > max_sum)
max_sum = sum;
} else {
assert(curr == N);
}
}
return max_sum;
}
int main ()
{
const int in_0[] = {-3,-4,1,2,3,-5,-6,4,-7,8,-9,-10,-1};
const int in_1[] = {1,2,3,-5,-6,4,-7,8,-9,-10,-1};
int max_sum_v0, max_sum_v1;
max_sum_v0 = maxSubArray_v1(in_0, 13);
assert(max_sum_v0 == 8);
max_sum_v1 = maxSubArray_v2(in_0, 13);
assert(max_sum_v1 == 8);
max_sum_v0 = maxSubArray_v1(in_1, 11);
assert(max_sum_v0 == 8);
max_sum_v1 = maxSubArray_v1(in_1, 11);
assert(max_sum_v1 == 8);
return 0;
}
import java.io.*;
import java.util.*;
public class MaxSubArray
{
private static class SubArray
{
int startIndex;
int endIndex;
int sum;
SubArray(int s, int e, int max)
{
startIndex = s;
endIndex = e;
sum = max;
}
}
public static void main(String[] args)
{
int [] arr = {-1, -1, -4, -1, -2, -1, 5, -3};//{-2, -3, 4, -1, -2, 1, 5, -3};
SubArray subArray = maxSubArray(arr);
if(subArray == null)
{
System.out.print("Either sub-array contains one element or "
+ "max sum > 0 does not exist for the given array");
return;
}
System.out.print("Max SubArray is : { ");
for(int i = subArray.startIndex; i<=subArray.endIndex; i++)
System.out.print(arr[i]+ ", ");
System.out.print(" } -- Max Sum is : "+subArray.sum);
}
static SubArray maxSubArray(int[] a)
{
int startIndex = -1;
int endIndex = -1;
int length = a.length;
int maxTillNow = 0;
int maxOverAll = 0;//Integer.MIN_VALUE;
for(int i = 0; i<length; i++)
{
maxTillNow += a[i];
if(maxTillNow < 0)
maxTillNow = 0;
if(maxOverAll < maxTillNow)
{
if(startIndex == -1)
startIndex = i;
endIndex = i;
maxOverAll = maxTillNow;
}
}
if(startIndex == -1 || startIndex == endIndex)
return null;
return new SubArray(startIndex, endIndex, maxOverAll);
}
}
package daily.practice.impl.misc;
public class HighestSum {
private static int solution(int arr[]){
int length = arr.length;
int highestSum = -100;
for(int i=0;i<length-1;i++){
int tempSum = arr[i] + arr[i+1];
if(tempSum>highestSum){
highestSum = tempSum;
}
}
System.out.println("[solution] Highest sum of two consecutive numer is: "+highestSum);
return highestSum;
}
public static void main(String args[]){
int arr[] = {-4,-1,-3,-2,-1};
System.out.println("[main] Highest sum is: " +solution(arr));
}
}
Python solution :
- Naman Dasot April 20, 2017