Design and analysis algorithm course Question 1 Consider an

Design and analysis algorithm course

Question 1: Consider an array of numbers. Give an algorithm that finds the maximum contiguous subarray that is increasing,

Remarks: In all the algorithms, always explain their correctness and analyze their complexity. The complexity should be as small as possible. A correct algorithm with large complexity, may not get full credit. Solve the following 5 questions.

Solution

The maximum contiguous subarray problem can be done simplly by scanning through all the array values and calculating at each position the maximum subarray ending at that particular position. We only need to taken care of ending position since the zeroth position is just after the last position at which the sum will be turn to negative.

I\'m doing C code for this as there is nothing particular language specify here.

Code complexity : O(n) ;

c code for maximum contiguous subarray:-

#include<stdio.h>

#define max(x,y) ( ((x) > (y)) ? (x) : (y) )

int maxSubArray(int array1[], int size)

{

int i=1;

int prevmax = array1[0];

int currmax = array1[0];

for (i=1 ; i<size ; i++)

{

currmax = max( array1[i],currmax +array1[i]);

prevmax= max (prevmax , currmax);

}

return prevmax;

}

int main()

{

int array1[] = { -2, 3, 1, 2, -3, 5, -3 };

int length = sizeof(array1)/sizeof(array1[0]);

int maximum = maxSubArray(array1,length);

printf(\"max contiguous will be %d\",maximum);

return 0;

}