Could you please help me with finding a test case that dosent work for the following:
https://www.codechef.com/viewsolution/45099425
Do we have to print only positive numbers(including 0) that makes a max sum?
what if input is -9 -10?
Access is denied - Code cannot be seen.
#include <stdio.h>
#include <stdlib.h>
struct tuple{
int low;
int high;
long long int sum;
};
struct tuple FindMaxSubArray(int low, int high, int *A);
struct tuple FindMaxCrossingSubArray(int low, int mid, int high, int *A);
int main(void)
{
int t, N, i, *A;
struct tuple ans;
scanf("%d", &t);
while(t–){
scanf("%d", &N);
A = (int )malloc (Nsizeof(int));
for(i =0; i < N; i++)
scanf("%d", A+i);
ans = FindMaxSubArray(0, N-1, A);
for(i = ans.low; i <= ans.high; i++)
printf("%d “, A[i]);
printf(”\n");
free(A);
}
return 0;
}
struct tuple FindMaxSubArray(int low, int high, int *A)
{
int mid = (low + high)/2;
struct tuple left, right, cross;
if(low == high){
left.low = low; left.high = high;
left.sum = A[low];
return left;
}
else{
left = FindMaxSubArray(low, mid, A);
right = FindMaxSubArray(mid+1, high, A);
cross = FindMaxCrossingSubArray(low, mid, high, A);
}
if(left.sum > right.sum && left.sum > cross.sum)
return left;
else if(right.sum > left.sum && right.sum > cross.sum)
return right;
else if(cross.sum > left.sum && cross.sum > right.sum)
return cross;
else if(left.sum == cross.sum && cross.sum == right.sum){
if(left.high - left.low >= cross.high - cross.low && left.high - left.low >= right.high - right.low)
return left;
else if(cross.high - cross.low > left.high - left.low && cross.high - cross.low >= right.high - right.low)
return cross;
else if(right.high - right.low > cross.high - cross.low && right.high - right.low > left.high - left.low)
return right;
}
else if(left.sum == right.sum){
if(left.high - left.low >= right.high - right.low)
return left;
else return right;
}
else if(left.sum == cross.sum){
if(left.high - left.low >= cross.high - cross.low)
return left;
else return cross;
}
else if(cross.sum == right.sum){
if(cross.high - cross.low >= right.high - right.low )
return cross;
else return right;
}
}
struct tuple FindMaxCrossingSubArray(int low, int mid, int high, int *A)
{
struct tuple ans;
int i, max_left;
long long int left_sum = -1000001, sum = 0;
for(i = mid; i >= low; i–){
sum += A[i];
if(sum > left_sum){
left_sum = sum;
max_left = i;
}
}
int max_right;
long long int right_sum = -1000001; sum = 0;
for(i = mid+1; i <= high; i++){
sum += A[i];
if(sum > right_sum){
right_sum = sum;
max_right = i;
}
}
ans.low = max_left; ans.high = max_right;
ans.sum = left_sum + right_sum;
return ans;
}
/* Linear algo. Knowing max subarray in A[1...j], deciding the max subarray in A[1...j+1], which is either the max subarray of A[1..j] or a subarray of form A[i...j+1], where 1 <= i <= j+1 */
#include <stdio.h>
#include <stdlib.h>
struct tuple{
int start, end;
long long int sum;
};
int main(){
int i, j, N, t, A, start, end;
long long int sum, max_sum_sofar;
scanf("%d", &t);
while(t–){
scanf("%d", &N);
A = (int)malloc(N *sizeof(int));
for(i=0; i < N; i++)
scanf("%d", A+i);
struct tuple ans;
j=0;
start =0; end =0; sum = A[0]; max_sum_sofar = A[0];
ans.start = start; ans.end = end; ans.sum = max_sum_sofar;
while(j+1 != N){
if(A[j+1] > sum && A[j+1] > sum + A[j+1]){ //sum <0 and a_i >=0
start = j+1; end = j+1;
sum = A[j+1];
}
else if(A[j+1] + sum >= sum && A[j+1] <= sum + A[j+1] ) //sum >=0 and a_i >=0
sum += A[j+1];
else if(A[j+1] + sum < sum ) // sum >=< 0 and a_i <0
sum += A[j+1];
if(sum > max_sum_sofar){
max_sum_sofar = sum; end = j+1;
ans.start = start; ans.end = end; ans.sum = max_sum_sofar;
}
else if(sum == max_sum_sofar){
end = j+1;
if(end - start > ans.end - ans.start){
ans.end = end; ans.start = start;
}
}
j++;
}
for(i= ans.start; i <= ans.end; i++)
printf("%d ", A[i]);
printf("\n");
free(A);
}
return 0;
}
Could you help me with this algorithm? What case fails?