Qn1: Write a C program to find the sum of contiguous subarray within a one dimensional (1-D) array of numbers which has the largest sum. Find the time complexty of your program.
Example:
-2 | -3 | 4 | -1 | -2 | 1 | 5 | -3 |
0 1 2 3 4 5 6 7
4 + (-1) + (-2) + 1 + 5 = 7
So the maximum contiguous subarray sum is 7
Program
#include<stdio.h>
#include<limits.h>
#include <time.h>
int main()
{
int n, x, y, max = INT_MIN;
printf("Enter array length: ");
scanf("%d", &n);
int a[n];
printf("Enter array: ");
for(int i=0; i<n; i++)
scanf("%d", &a[i]);
clock_t start,end;
double total_cputime;
start=clock();
for(int i=0; i<n-1; i++)
{
for(int j=i+1; j<n; j++)
{
int count = 0;
for(int k=i; k<j; k++)
{
count = count + a[k];
}
if(count > max)
{
max = count;
x = i, y = j-1;
}
}
}
end=clock();
total_cputime=((double)(end-start))/CLOCKS_PER_SEC;
printf("Max sum array range: %d to %d (both inclusive)\nMax sum of the subsequence: %d", x,y,max);
printf("\nTotal time taken: %lf", total_cputime);
}
Output
Qn2: Write a program to find out the largest difference between two elements A[i] and A[j] ( A[j]-A[i]) of the array of integers A in O(n) time such that j > i. For example: Let A is an array of integers:
int[] a = { 10, 3, 6, 8, 9, 4, 3 };
if i=1, j=3, then diff = a[j] – a[i] = 8 – 3 = 5
if i=4, j=6, then diff = a[j] – a[i] = 3 – 9 = -6
………
………
if i=1, j=4, then diff = a[j] – a[i] = 9 – 3 = 6
………
………
6 is the largest number between all the differences, that is the answer.
Find the time complexty of your program.
Program
#include<stdio.h>
#include<limits.h>
#include <time.h>
int main()
{
int n, x, y, max = INT_MIN;
printf("Enter array length: ");
scanf("%d", &n);
int a[n];
printf("Enter array: ");
for(int i=0; i<n; i++)
scanf("%d", &a[i]);
clock_t start,end;
double total_cputime;
start=clock();
for(int i=0; i<n-1; i++)
{
for(int j=i+1; j<n; j++)
{
if(a[j]-a[i] > max)
{
x = i;
y = j;
max = a[j]-a[i];
}
}
}
end=clock();
total_cputime=((double)(end-start))/CLOCKS_PER_SEC;
printf("Max sum array range: %d to %d (both inclusive)\nMax sum of the subsequence: %d", x,y,max);
printf("\nTotal time taken: %lf", total_cputime);
}
Output
