Microsoft Interview Question
SDE-2sTeam: STB and MVO
Country: India
Interview Type: In-Person
void maxsum(int *a,int n){
int max_so_far=a[0],max_end_here=a[0];
int start,end,temp_start,i;
for(i=0;i<n;i++){
if(max_end_here<0){
max_end_here=a[i];
temp_start=i;
}
else
max_end_here += a[i];
if(max_end_here>max_so_far){
max_so_far=max_end_here;
start=temp_start;
end=i;
}
}
printf("( %d , %d ) %d",start,end+1,max_so_far);
return;
}
using System;
class Program
{
public static void Main(){
int[] a = {1,2,3,-3,4};
int n = a.Length;
int maxSum = 0;
for(int i=0;i<n;i++)
{
for(int j=i+1; j<n;j++)
{
int k=i;
int workingSum = 0;
while(k <= j)
{
workingSum += a[k];
k++;
}
if(workingSum > maxSum)
maxSum = workingSum;
}
}
Console.WriteLine(maxSum);
}
}
if a[i] < a[i] + a[i-1] then
a[i] = a[i] + a[i-1] for all i>0 and then find maximum
time complexity = O(n)
and no extra memory required
public class ArrayMaxSum {
/**
* @param args
*/
public static void main(String[] args) {
String string = "1,2,-10,3,4,-20,5,6,4,-50,9,0,-1";
String[] numbers = string.split(",");
LinkedList<String> lst = new LinkedList<String>();
LinkedList<String> tmp = new LinkedList<String>();
int max_so_far = 0;
int max_ending_here = 0;
for (int i = 0; i < numbers.length-1; i++)
{
max_ending_here = max_ending_here + Integer.parseInt(numbers[i]);
lst.add(numbers[i]);
if (max_ending_here < 0)
{
max_ending_here = 0;
lst.clear();
}
if (max_ending_here > max_so_far)
{
tmp.clear();
max_so_far = max_ending_here;
tmp.addAll(lst);
}
}
for(String str : tmp)
{
System.out.print(str+", ");
}
System.out.print(" = "+max_so_far);
}
}
using System;
namespace Algorithms
{
class Program
{
static void Main(string[] args)
{
Program p = new Program();
int[] array = { 31, -41, 59, 26, -53, 58, 97, -93, -23, 84 };
int result = p.ArrayMaxSum(0, array.Length - 1, array);
Console.Write(result.ToString());
Console.ReadKey();
}
public int ArrayMaxSum(int lowerBound, int upperBound, int[] array)
{
if (lowerBound > upperBound)
return 0;
if ( lowerBound == upperBound )
{
return Math.Max(0,array[lowerBound]);
}
int mid = (lowerBound + upperBound) / 2;
int sum = 0;
int lmax = 0;
for (int i = mid; i >= lowerBound; i--)
{
sum = sum + array[i];
lmax = Math.Max(lmax, sum);
}
sum = 0;
int rmax = 0 ;
for (int i = mid+1 ; i <= upperBound; i++)
{
sum = sum + array[i];
rmax = Math.Max(rmax, sum);
}
return Math.Max((lmax + rmax), Math.Max(ArrayMaxSum(lowerBound, mid, array), ArrayMaxSum(mid + 1, upperBound, array)));
}
}
}
public static Boolean FindMaxSusequenceSum(int[] N, int first, int last, ref int sum, ref int start, ref int end )
{
if (N == null) return false;
if(N.Length<=last || first>last) return false;
if(first==last)
{
sum = N[first];
start = first;
end = last;
return true;
}
int r_sum=0;
int r_start=0;
int r_end=0;
FindMaxSusequenceSum(N, first + 1, last, ref r_sum, ref r_start, ref r_end);
if (N[first] > r_sum)
{
sum = N[first];
start = first;
end = first;
}
else if (r_start == first + 1)
{
if (N[first] >= 0)
{
sum = r_sum + N[first];
start = first;
end = r_end;
}
else
{
sum = r_sum;
start = r_start;
end = r_end;
}
}
else if( r_start > first+1 )
{
int sum2 = 0;
for (int i = first; i < r_start; i++)
{
sum2 += N[i];
}
if (sum2 >= 0)
{
sum = sum2 + r_sum;
start = first;
end = r_end;
}
else
{
sum = r_sum;
start = r_start;
end = r_end;
}
}
return true;
}
public static Boolean FindMaxSusequenceSum(int[] N, int first, int last, ref int sum, ref int start, ref int end )
{
if (N == null) return false;
if(N.Length<=last || first>last) return false;
if(first==last)
{
sum = N[first];
start = first;
end = last;
return true;
}
int r_sum=0;
int r_start=0;
int r_end=0;
FindMaxSusequenceSum(N, first + 1, last, ref r_sum, ref r_start, ref r_end);
if (N[first] > r_sum)
{
sum = N[first];
start = first;
end = first;
}
else if (r_start == first + 1)
{
if (N[first] >= 0)
{
sum = r_sum + N[first];
start = first;
end = r_end;
}
else
{
sum = r_sum;
start = r_start;
end = r_end;
}
}
else if( r_start > first+1 )
{
int sum2 = 0;
for (int i = first; i < r_start; i++)
{
sum2 += N[i];
}
if (sum2 >= 0)
{
sum = sum2 + r_sum;
start = first;
end = r_end;
}
else
{
sum = r_sum;
start = r_start;
end = r_end;
}
}
return true;
}
- Vir Pratap Uttam May 12, 2015