Bloomberg LP Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
You are given an array of integers both negative and positive.
Print the maximum continuous sum of the array and if all the elements are negative, print the smallest of them.
Ex : [-20, -5, -2, -9] :> -2(-2)
If you want the smallest among the negative numbers array, then in the above example, -20 is the smallest.
Iterate through the array and check keep calculating the running sum by adding the current value.
If the running sum is greater than the maxSum then update the maxSum and after that if the current value is greater than maxSum then update maxSum and running sum as current value.
Special handling of all negative values. If all negative check if maxSum is < currentvalue and update the maxSum and running sum.
int getMaxSum(int [] array){
int maxSum=array[0];
int startIdx =0;
int endIdx = 0;
int runningSum = maxSum;
boolean allNegative = false;
if(maxSum<0){
allNegative = true;
}
for(int i=1;i<array.length;i++){
allNegative = allNegative && (array[i]<0);
if(!allNegative){
runningSum+=array[i];
if(runningSum > maxSum){
maxSum = runningSum;
endIdx = i;
if(array[i]>maxSum){
startIdx=i;
endIdx=i;
maxSum=array[i];
runningSum=array[i];
}
}
}else{
if(maxSum < array[i]){
maxSum = array[i];
runningSum = array[i];
startIdx=i;
endIdx=i;
}
}
}
System.out.println("Max Sum::" + maxSum);
System.out.println("Start Idx ::" + startIdx + " End Inx :: " + endIdx);
return maxSum;
}
A solution with .NET 3.5 and LINQ. I think the smallest number in the last example should be -20 but I added a solution for smallest absolute value just in case.
private static void SumArray(int[] input)
{
// Get the sum
Console.WriteLine(input.Sum().ToString());
if (input.All(a => a < 0))
{
// Get the smallest number
Console.WriteLine(input.Min().ToString());
// Get the smallest absolute value
var newList = new List<int>();
foreach (var item in input)
{
newList.Add(Math.Abs(item));
}
Console.WriteLine(newList.Min() * (-1));
}
}
public static int[] run(int[] src) {
int start = 0, end = 0;
long max = src[0], sum = 0;
for (int index = 1; index < src.length; index++) {
if (max <= 0 && src[index] > max) {
max = src[index];
start = end = index;
sum = 0;
}
if (max > 0) {
if (src[index] >= 0) {
if (sum < 0) {
sum += src[index];
if (sum >= 0) {
end = index;
max += sum;
}
} else {
end = index;
max += src[index];
}
} else {
sum += src[index];
}
}
}
int[] result = new int[end - start + 1];
System.arraycopy(src, start, result, 0, end - start + 1);
return result;
}
tested with the test case and some variations(some or all numbers changed to negative), more test cases needed
C# using kadane's algorithm
public void LargestSumOfContiguousArray(int[] array)
{
var ans = 0;
var maxAtElement = 0;
var isAllNegative = true;
var minNumberOfArray = int.MinValue;
for (var i = 0; i < array.Length; i++)
{
isAllNegative &= array[i] < 0;
minNumberOfArray = Math.Max(minNumberOfArray, array[i]);
maxAtElement = Math.Max(maxAtElement + array[i], array[i]);
ans = Math.Max(maxAtElement, ans);
}
if (isAllNegative)
Console.WriteLine(minNumberOfArray);
else
Console.WriteLine(ans);
}
int MaxSubarray(vector<int> const &a)
{
int max_sum = numeric_limits<int>::min();
int sum = 0;
int head_sum = 0;
for (int i = 0; i < a.size(); ++i) {
sum += a[i];
if (i > 0) {
head_sum += a[i - 1];
if (head_sum < 0) {
sum -= head_sum;
head_sum = 0;
}
}
max_sum = max(max_sum, sum);
}
return max_sum;
}
I guess I can help you with a python code-
### The code for finding maximum sum subarray in an array
###In this case I am assuming that the maximum subarray has to be atleast length 1
arr = map(int , raw_input().split())
ans = arr[0]
max_ending_here = arr[0]
for i in arr[1:]:
max_ending_here = max(max_ending_here + i , i)
ans = max(max_ending_here ,ans)
print ans
Shouldn't the output of last input be this - Ex : [10, -3, 4, -2, -1, 10] -> 18 (10, -3, 4, -2, -1, 10)
- velu007 April 07, 2017Or did I misunderstood the question ?