Microsoft Interview Question
Applications DevelopersCountry: United States
Interview Type: In-Person
Then it depends. Does your definition of sub-sequence consists of the empty sequence? Is the sum of the empty sequence 0? Then answer is 0.
If you don't allow empty sequence, then pick the largest number.
Sub array means contiguous blocks and sub sequence means the elements may or may not be contiguous.
then i actually mean sub-array. Is there a way to change my question or may be drop this one and add a more appropriate one?
int find_max_sum(int *arr, int n)
{
int current_max, max_so_far,i;
int start=0,end =0;
current_max= max_so_far=0;
for(i=0;i<n,i++)
{
max_so_far+=a[i];
if(max_so_far<0){
max_so_far=0;start =++i;}
if(current_max<max_so_far)
{ current_max=max_so_far;
end = i;}
}
}
for(i=start;i<=end;i++)
printf("%d",arr[i]);
return;
Use dutch national flag algorithm. One thing is that it destroys the original array.
#include <stdio.h>
#include <limits.h>
void swap (int *a, int *b) {
int temp = *a ;
*a = *b ;
*b = temp ;
}
int maxSubSequence (int a[], int size) {
int i, high = size-1, start = 0, mid = 0;
int sum = 0, mid_flag = 0, max_min = INT_MIN;
/* Similar to dutch national flag */
while ( mid < high ) {
if ( a[mid] < 0 ) {
swap (&a[start], &a[mid]);
/* check for maximum of minimum */
if ( max_min < a[start] )
max_min = a[start] ;
start ++ ;
mid ++ ;
} else if ( a[mid] == 0 ) {
mid_flag = 1 ; /* denotes there is atleast one zero */
mid ++ ;
}
else {
swap (&a[mid], &a[high]) ;
sum += a[high] ; /* adds the sum */
high -- ;
}
}
if ( sum )
return sum ;
if ( mid_flag )
return 0 ;
return max_min ; // returns the maximum of all negative numbers
}
int main () {
int a[] = {-4, -9, 0, -3, -1, -2, 0, -2, -8} ;
int size = sizeof(a) / sizeof(a[0]) ;
printf ( "\nMaximum sum sub-sequence : %d\n", maxSubSequence(a,size)) ;
return 0 ;
}
for an array maintain a sum array where sum[i] will be sum of all elements from 0 to i-1
Once you do that, find out the 2 elements in this array whose difference is max.
for example
array 1 2-1 -9 11 23 0
sum 0 1 3 2 -7 4 27 27
here it will be 27 and -7 so answer would be subarray from index 4 to 6. There could be bugs regarding choosing right index but i hope you got the idea.
- Kadane's solution... O(n) time and O(1) space...
int find_max_sum(int *arr, int n)
{
int current_max, max_so_far,i;
current_max= max_so_far=0;
for(i=0;i<n,i++)
{
max_so_far+=a[i];
if(max_so_far<0)
max_so_far=0;
if(current_max<max_so_far)
current_max=max_so_far;
}
}
i forgot to insert the return stmt... after the loop exits, the value of current_max needs to be returned !
This gives max sub sequence sum, not the sequence itself. Should return start and end indices.
What if the sequence is "-2 , -1" ? For a sequence of negative numbers the answer would be zero i suppose as per the code.
All the numbers are negative case is the only special case,you can check for all the numbers are negative or not if negative return small negative integer otherwise proceed with kandens algo
If we keep
if(current_max<max_so_far)
current_max=max_so_far;
before checking less than 0 condition we can handle the all negative value input also
pair<int, int> max_sub_sequence(const vector<int>& data) {
int curr_sum = 0;
int curr_start = 0;
int max_sum = -numeric_limits<int>::max();
pair<int, int> max_seq = make_pair(-1,-1);
for (int i = 0; i < data.size(); i++) {
curr_sum += data[i];
if (curr_sum > max_sum) {
max_sum = curr_sum;
max_seq = make_pair(curr_start, i+1);
}
if (curr_sum < 0) {
curr_sum = 0;
curr_start = i+1;
}
}
return max_seq;
}
public static int maximumSubArray(int[] array)
{
int max= array[0]>0?array[0]:0;
int trail= max;
for(int i=1; i<array.length; i++)
{
trail= trail + array[i]>array[i]? trail+array[i] : array[i];
max= max>trail?max:trail;
}
return max;
}
int max= array[0]>0?array[0]:array[0]-1;
would work if all the terms in the array are negative
#include "stdio.h"
#include "conio.h"
int main(){
int a[10]={-10,-2,3,-4,5,-1,0,8,-8,-11};
int max=a[0]-1;
int i,j,start,end,sum=0;
for(i=0;i<10;i++){
sum=0;
for(j=i;j<10;j++){
sum=sum+a[j];
if(sum>max){
max=sum;
start=i;
end=j;
}
}
}
printf("Max of the integers is %d starts at %d to %d ",max,start,end);
getch();
}
#include<stdio.h>
int p1,p2;
int maxsubarr(int arr[],int s)
{
int max=0,i,j,z,max_neg=arr[0];
int max_so_far=0;
for(j=1;j<s;j++)
{
if(arr[j]<0)
{
if(arr[j]>=max_neg)
{max_neg=arr[j];
p1=p2=j;}
}
else
break;
if(j==s-1)
{
return max_neg;}
}
if(j!=s-1){
for(i=0;i<s;i++)
{
max_so_far+=arr[i];
if(max_so_far<0)
{
max_so_far=0;
//z=i;
p1=i+1;
}
else if(max<max_so_far)
{
//if(z==i+1)
//p1=i;
max=max_so_far;
p2=i;
}
}
return max;
}
}
int main()
{
int s,p,i,max_neg;
int arr[]={-22,-6,-7,-41,-11,-51};
s=sizeof(arr)/sizeof(arr[0]);
printf("%d\n",maxsubarr( arr, s));
for(p=p1;p<=p2;p++)
printf("%d ",arr[p]);
//if all elements are negative
return 0;
}
//i think recursion is best suited for this
#include<stdio.h>
#define SIZE 8
int max_left_index;
int max_right_index;
int max_sub_array(int A[],int,int);
int max_sub_crossing(int A[],int,int,int);
int main()
{
int A[SIZE],i,j;
printf("enter the element in the aarry");
for(i=0;i<SIZE;i++)
{
scanf("%d \n",&A[i]);
}
int low,high,mid;
low=0;
high=SIZE-1;
mid=(low+high)/2;
int s=max_sub_array(A,low,high);
printf("The max sum=[%d] \n",s);
printf("index of sax array=[i=%d]""[j=%d]",max_left_index,max_right_index);
return 0;
}
int max_sub_array(int A[],int low,int high)
{
int a,b,c,mid;
if(low==high)
return(A[low]);
else
{
mid=(low+high)/2;
a=max_sub_array(A,low,mid);
b=max_sub_array(A,mid+1,high);
c=max_sub_crossing(A,low,mid,high);
}
if(a>=b&&a>=c)
return(a);
else if(b>=a&&b>=c)
return(b);
else if(c>=a&&c>=b)
return(c);
}
int max_sub_crossing(int A[],int low,int mid, int high)
{
int i,j,k;
int leftsum=-10000000;
int sum=0;
for(i=mid;i>=low;i--)
{
sum=sum+A[i];
if(sum>leftsum)
{
leftsum=sum;
max_left_index=i;
}
}
int rightsum=-10000000;
sum=0;
for(j=mid;j<=high;j++)
{
sum=sum+A[j];
if(sum>=rightsum)
{
rightsum=sum;
max_right_index=j;
}
}
return(leftsum+rightsum);
}
The following function satisfy for all the cases.
int findMaxSubArraySum(int[] arr) {
int r=0, s=0;
for(int i = 0; i < arr.length; i++) {
s += arr[i];
if(r < s)
r = s;
else
s = 0;
}
return r;
}
int _tmain(int argc, _TCHAR* argv[])
{
int array[] = {80,18,-56453,53,14,90,80,-70,100,105};
int size_of_array = sizeof(array);
std::cout<<"size_of_array"<<size_of_array<<std::endl;
int size_of_int = sizeof(int);
std::cout<<"size_of_int"<<size_of_int<<std::endl;
int n = sizeof(array)/sizeof(int);
int max_sum=0;
int sum=0;
for(int i = 0; i < n; i++)
{
//if (sum+array[i]>=max_sum) {sum=sum+array[i]; max_sum=sum;}
if (array[i]+array[i+1]>=max_sum) {sum=array[i]+array[i+1]; max_sum=sum;}
else sum=0;
}
std::cout<< max_sum;
getchar();
return 0;
}
if sub-sequence then take all positive integers.
- Anonymous August 25, 2012if sub-array, then this is a classic problem.