PayPal Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
Out put for folloing input is wron.{-1,-2,3,4}.Expected out put is 7 but it's giving six.
int main(){
int array[] = {80,18,-56453,53,14};
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;}
else sum=0;
}
cout<< max_sum;
}
This code fails for the below case where a big positive number is followed by a smaller negative number and again a set of positive numbers.
e.g. -1, -11, -2, 3, -5, 10, -1, 3, 2, 1
Here the subarry with max sum is 10, -1, 3, 2, 1 but your code recognizes it as 10 !!
int LargestSum(int* index, int size, int* startIndex, int* endIndex){
int i;
int max_so_far, max_ending_here;
max_so_far= INT_MIN;
max_ending_here = 0;
for(i=0; i< size;i++){
max_ending_here=max_ending_here + index[i];
if(index[i] > max_ending_here){
max_ending_here = index[i];
*startIndex = i;
}
if(max_ending_here > max_so_far){
max_so_far = max_ending_here;
*endIndex = i;
}
printf("%d, %d\n", max_so_far, max_ending_here);
}
//printf("%u, %u\n",startIndex,endIndex);
//printf("%d, %d\n",*startIndex,*endIndex);
return max_so_far;
}
int main(){
int arr[8] = {-2, -3, 4, -1, -2, 1, 5, -3};
int size = sizeof(arr)/sizeof(arr[0]);
int start=0, end=7;
//printf("%u, %u\n",&start,&end);
printf("Starts at:%d, Ends at:%d,Largest Sum:%d\n",start, end, LargestSum(arr,size, &start, &end));
}
This code works for Negative Numbers also and also gives startIndex and endIndex of the Maximum SubArray
int LargestSum(int* index, int size, int* startIndex, int* endIndex){
int i;
int max_so_far, max_ending_here;
max_so_far= INT_MIN;
max_ending_here = 0;
for(i=0; i< size;i++){
max_ending_here=max_ending_here + index[i];
if(index[i] > max_ending_here){
max_ending_here = index[i];
*startIndex = i;
}
if(max_ending_here > max_so_far){
max_so_far = max_ending_here;
*endIndex = i;
}
printf("%d, %d\n", max_so_far, max_ending_here);
}
//printf("%u, %u\n",startIndex,endIndex);
//printf("%d, %d\n",*startIndex,*endIndex);
return max_so_far;
}
int main(){
int arr[8] = {-2, -3, 4, -1, -2, 1, 5, -3};
int size = sizeof(arr)/sizeof(arr[0]);
int start=0, end=7;
//printf("%u, %u\n",&start,&end);
printf("Starts at:%d, Ends at:%d,Largest Sum:%d\n",start, end, LargestSum(arr,size, &start, &end));
}
#include<iostream>
using namespace std;
#include<stdio.h>
int maxSubArraySum(int a[], int size)
{
int max_so_far = 0, max_ending_here = 0;
int i;
for(i = 0; i < size; i++)
{
max_ending_here = max_ending_here + a[i];
if(max_ending_here < 0)
max_ending_here = 0;
if(max_so_far < max_ending_here)
max_so_far = max_ending_here;
}
return max_so_far;
}
/*Driver program to test maxSubArraySum*/
int main()
{
int a[] = {-2, 10,-13, 4, 7, -6, 1, 5, -3};
int max_sum = maxSubArraySum(a, 8);
printf("Maximum contiguous sum is %d\n", max_sum);
return 0;
}
int maxSumInSubArr(int array[], int size, int *startI, int *stopI)
{
int max_here, max_far;
max_far = INT_MIN;
max_here = 0;
int tmpStart = *startI;
for (int i=0; i < size; i++) {
max_here = max_here + array[i];
if(array[i] > max_here)
{
max_here = array[i];
tmpStart = i;
}
if(max_here > max_far)
{
max_far = max_here;
*stopI = i;
*startI = tmpStart;
}
}
return max_far;
}
I have written this code. I have taken the size of the array to be 20. You change it according to your need.
#include<iostream>
using namespace std;
int maxcross(int arr[],int low,int mid,int high){
int left_sum = -1,sum=0,max_left,right_sum=-1,;
for(int i=mid;i>=low;i--){
sum+=arr[i];
if(sum>left_sum){
left_sum=sum;
max_left = i;
}
}
sum=0;
for(int i=mid+1;i<=high;i++){
sum+=arr[i];
if(sum>right_sum){
right_sum = sum;
}
}
return left_sum+right_sum;
}
int max_sub_array(int arr[],int low,int high){
if(high==low)
return arr[low];
else{
int mid = (low+high)/2;
int left_sum = max_sub_array(arr,low,mid);
int right_sum = max_sub_array(arr,mid+1,high);
int cross_sum = maxcross(arr,low,mid,high);
if(left_sum>right_sum&&left_sum>cross_sum)
return left_sum;
else if(right_sum>cross_sum)
return right_sum;
else
return cross_sum;
}
}
int main(){
int arr[20];
cout<<"Enter the size of the array(max 20):\n";
int n;cin>>n;
cout<<"Enter the array:\n";
for(int i=0;i<n;i++)
cin>>arr[i];
int ans = max_sub_array(arr,0,n-1);
cout<<"The Maximum sum is: "<<ans<<endl;
return 0;
}
Have any queries. Please comment
package amazonExcerise;
import java.util.Arrays;
import java.util.Collections;
public class TestNGValidation {
public static void main(String[] args) {
int a[]={-1, -11, -2, 3, -5, 10, -1, 3, 2, 1};
int[] b = new int[500];
int k=0,Result=0;
for(int i=0;i<=a.length-1;i++){
Result=0;
for(int j=i;j<=a.length-1;j++,k++){
Result=a[j]+Result;
b[k]=Result;
}
}
Arrays.sort(b);
System.out.println("The maximum sum possible from different sub Arrays : "+b[b.length-1]);
}
}
Working code
int main(){
int array[] = {18,-18, -53, 53, 4};
int n = sizeof(array)/sizeof(int);
printf("\n Length-- %d --i \n",n);
int max_sum=0;
int sum=0;
for(int i = 0; i <= n; i++) {
sum+=array[i];
if(sum>max_sum){
max_sum=sum;}
else if (sum < 0) {
sum = 0;
}
}
printf("\n -> %d \n",max_sum);
}
~
Hi, wont ur code fail if the first number in the array is a -ve. I guess the following code works!
int main(){
int array[] = {80,18,-56453,53,14};
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;}
else sum=0;
}
cout<< max_sum;
}
@silivimass -
This code fails for the below case where a big positive number is followed by a smaller negative number and again a set of positive numbers.
e.g. -1, -11, -2, 3, -5, 10, -1, 3, 2, 1
Here the subarry with max sum is 10, -1, 3, 2, 1 but your code recognizes it as 10 !!
- hello world January 23, 2012