Microsoft Interview Question
SDE1sCountry: United States
Interview Type: In-Person
public static find_max_subarray(int[] a) {
// check arguments
if(a == null || a.Length == 0) throw new ArgumentNullException();
int max = a[0], tmp_max = a[0];
foreach(var i in a) {
if(tmp_max < 0) {
tmp_max = i;
} else {
tmp_max += i;
}
max = tmp_max > max ? tmp_max : max;
}
}
int main ()
{
int arr[] = {-23, -45, 78, 67, 45, 78, 23, -67, -45};
int max_sum = 0, max_pos = 0, max_sz = 0;
int arr_sz = sizeof(arr)/sizeof(int);
for(int i=0; i < arr_sz; i++)
{
int sum = 0;
int cur_sz = arr_sz - i;
for(int j=0; j < cur_sz; j++)
{
sum += arr[i + j];
if(sum > max_sum)
{
max_sum = sum;
max_pos = i;
max_sz = j + 1;
}
}
}
for(int i = max_pos; i < max_pos+max_sz; i++)
printf("%d ", arr[i]);
}
int subseq (int array[], int length) {
int sum[length], i, j, max;
sum[0] = array[0];
for (i=1;i<length;i++) {
j = i - 1;
while (j >= 0) {
if (array[j] < array[i]
&& (sum[j] + array[j]) > sum[i]) {
sum[i] = sum[j] + array[j];
}
--j;
}
}
max = sum[0];
for (i=1;i<length;i++) {
if (max < sum[i])
max = sum[i];
}
return max;
}
static int[] Subsequence(int[] A)
{
int maxStart = 0;
int maxEnd = A.Length - 1;
int maxSum = 0;
int start = -1;
int end = 0;
int sum = 0;
for(int i = 0; i < A.Length; i++)
{
if(A[i] >= 0 && start < 0)
{
start = i; end = i; sum=A[i];
}
else if(A[i] >= 0 && start >= 0)
{
end = i; sum += A[i];
}
else if (A[i] < 0 && start >= 0)
{
if(sum > maxSum)
{
maxSum =sum;
maxStart= start;
maxEnd = end;
}
start = -1;
}
}
//last sum
if (start >= 0 && sum > maxSum)
{
maxSum = sum;
maxStart = start;
maxEnd = end;
}
return new int[]
{
maxSum,
maxStart,
maxEnd
};
}
public static int MaxSequenceSum(int[] nums)
{
if (nums == null || nums.Length == 0)
{
throw new ArgumentException();
}
if (nums.Length == 1)
{
return nums[0];
}
int sum = 0;
int maxSum = nums[0];
int lastEnd = 0;
for (int i = 0; i < nums.Length; i++)
{
if (nums[i] > 0 && lastEnd == i - 1)
{
sum += nums[i];
++lastEnd;
}
else if (nums[i] > 0 && lastEnd < i - 1)
{
sum = nums[i];
lastEnd = i;
}
else if (nums[i] < 0)
{
if (lastEnd != 0)
{
if (maxSum < sum)
{
maxSum = sum;
}
}
else
{
if (maxSum < nums[i])
{
maxSum = nums[i];
}
}
}
}
return maxSum;
}
Divided algo in few parts:
part 1:
1) get minimum negative value
2) get first positive sum of array
3) get start & end index of first positive sum
this will be current running sum
part 2:
1) get sum of all negative values
2) get sum of all positive values
3) compare current_sum with curr_sum + positive_sum + negative_sum
if max_sum < (curr_sum + positive_sum + negative_sum)
update max_sum
else
update curr_sum
if max_sum < positive sum
update max_sum with positive sum
4) also keep on updating indexes
I have written code, due to keep track of index, code has become little messy
please update me with compact code, if u have
void maxSubSeq (int *a, int n)
{
int max = -1;
int i = 0;
int max_e_i = 0;
int cur_s_i = 0;
int cur_e_i = 0;
int pos = 0;
int neg = 0;
int cur = -1;
int max_s_i = -1;
int l_n_v = -10000;
int next_p_index = 0;
int neg_i = 0;
while (i < n)
{
if (a[i] < 0 && a[i] > l_n_v && cur < 0)
{
l_n_v = a[i];
neg_i = i;
i++;
continue;
}
if (cur > 0 && a[i] < 0)
break;
if (a[i] >= 0)
{
cur = 0;
while (i < n && a[i] >= 0)
{
if (max_s_i < 0)
max_s_i = i;
cur += a[i];
i++;
}
break;
}
i++;
}
if (cur >= 0)
{
max = cur;
max_e_i = i-1;
}
while (i < n)
{
neg = 0;
pos = 0;
while (i < n && a[i] < 0)
{
neg += a[i];
i++;
}
if (i < n)
next_p_index = i;
while (i < n && a[i] > 0)
{
pos += a[i];
i++;
}
if ((cur + neg + pos) > max)
{
cur = max = cur+neg+pos;
cur_e_i = max_e_i = i-1;
}
else
{
cur = cur+pos+neg;
cur_e_i = i-1;
}
if (max < pos)
{
cur = max = pos;
cur_s_i = max_s_i = next_p_index;
}
}
if (max == -1)
{
printf ("no Positive sum. Least negative value is: %d at index: %d\n", l_n_v, neg_i);
}
else
{
printf ("Max sum is: %d\n", max);
printf ("Max SubSequence is: \n", max);
for (i = max_s_i; i <= max_e_i; i++)
printf ("%d ", a[i]);
printf ("\n");
}
}
I have run it for the following test cases:
int a[] = {-1,-2,1,3,11,-10,-3,1,-9,2,11,13,-11,25};
int a[] = {10,11,-15,-20,2,3,-7,15,30,-1,10,-1,30};
int a[] = {-20,-30,-40,-2,-9,-13};
int a[] = {-20,-30,-40,-1,0,-9,-13};
int a[] = {3,4,-3,1,-2,1,-1,-1,-1,-1,-1};
int a[] = {3,4,-3,1,-2,25,-1,-1,-1,-1,-1};
Update me for other tricky cases :)
//@saurabh. Your code looks good but you have used too many variables. Here is a simple one. Mine doesn't work for all -ve numbers because you don't need to handle that case because you won't have a seq in -ve numbers.
int* subseq(int *array, int length) {
int i = 0, max = 0;
int* new_array = (int *)malloc(sizeof(int*(length+1)));
new_array[0] = 0;
if (array == NULL || length == 0)
return;
for(i=0;i<length;i++) {
if((new_array[i] + array[i]) >= 0) {
new_array[i+1] = new_array[i] + array[i];
max = (max >= new_array[i+1]) ? max : new_array[i+1];
}
else
new_array[i+1] = 0;
}
return new_array;
}
This code find the max sum with the locations:
public void maxSubSeq(int[] data){
int s = 0, a = 0, b = 0, sum = 0, maxSum = 0;
for(int i = 0; i < data.length; i++){
sum = sum + data[i];
if(sum < 0){
sum = 0;
s = i + 1;
}
else if(sum > maxSum){
maxSum = sum;
a = s;
b = i;
}
}
System.out.println("Max sum is: " + maxSum + " from location " + a + " to " + b);
}
I don't understand your code. I think you need 3 loops. At least my Code works.
struct index
{
int index_left,index_right;
};
index findLargestSubsequence(int arr[],int len)
{
int index_left=0;
int index_right=0;
int max_sum=0;
int sum = 0;
index my_index;
for(int i = 0 ; i<len ; i++)
{
for( int k = i ;k<len ; k++)
{
for( int j = i ; j<=k ; j++)
{
sum += arr[j];
}
if(sum > max_sum)
{
max_sum = sum;
index_left = i;
index_right = k;
}
sum=0;
}
}
my_index.index_left = index_left;
my_index.index_right = index_right;
return my_index;
}
public static long maxSumSequence(int[] arr){
long sum = arr[0];
long oldsum = arr[0];
for (int i = 1; i < arr.length; i++){
long newsum = arr[i], tempsum = sum + arr[i];
if(tempsum < sum){
if (oldsum < sum) oldsum = sum;
sum = newsum;
}else{
if ((newsum > tempsum) && (newsum > sum)) sum = newsum;
if ((tempsum > sum) && (tempsum > newsum)) sum = tempsum;
}
}
if (sum > oldsum)return sum;
return oldsum;
}
If all the elements are -ve than print the one having smallest magnitude
else
take into account only +ve numbers.
- Sarthak Mall June 02, 2013