Ques 9 .

Maximum Value Contiguous Subsequence: Given a sequence of n

numbers A(1) ...A(n), give an algorithm for finding a contiguous subsequence A(i)
...A(j) for which the sum of elements in the subsequence is maximum.
Example : {-2, 11, -4, 13, -5, 2} → 20 and {1, -3, 4, -2, -1, 6 } → 7.

Algorithm 1 :

Kadane’s Algorithm

●​ Firstly we will make two variables Max_sum and current_sum.

●​ Max_sum to store the maximum sum found so far.
●​ Current_sum to store the sum of the current subarray.
●​ Then we will iterate the array by adding the current element to Current_sum
●​ If Current_sum becomes greater than Max_sum, update Max_sum.
●​ If Current_sum becomes negative, reset it to 0. (since starting a new subarray
may be better).
Code :

#include <stdio.h>
#include <limits.h>

void array_sum(int arr[], int n) {

int max_sum = INT_MIN;
int current_sum = 0;
int start = 0, end = 0, temp_start = 0;

for (int i = 0; i < n; i++) {

current_sum += arr[i];

if (current_sum > max_sum) {

max_sum = current_sum;
start = temp_start;
end = i;
}

if (current_sum < 0) {
current_sum = 0;
temp_start = i + 1;
}
}
printf("Maximum subarray sum: %d\n", max_sum);
printf("Subarray: ");
for (int i = start; i <= end; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}

int main() {
int arr[] = {-2, 11, -4, 13, -5, 2};
int n = sizeof(arr) / sizeof(arr[0]);

array_sum(arr, n);

return 0;
}

Code :

Output :
Algorithm 2 :
Dynamic Programming Approach
​
Algorithm 2:

●​ Stores the maximum subarray sum ending at index i dp[i].

●​ Keeps track of the maximum sum found ,max_sum = arr[0].
●​ Track indices of the max subarray start = 0 , end = 0 , temp_start = 0 .
●​ Iterate the Array through 1 to n-1.
●​ If arr[i] alone is greater than dp[i-1] + arr[i] , start a new subarray:
dp[i] = arr[i]; temp_start = i.
●​ If not possible then extend the previous subarray dp[i] = dp[i-1] + arr[i].
●​ If dp [i] > max_sum, update max_sum , start = temp_start, and end = i.

Code :

#include <stdio.h>
#include <limits.h>

void max_subarray_dp(int arr[], int n) {

int max_sum = INT_MIN;
int current_sum = 0;
int start = 0, end = 0, temp_start = 0;

for (int i = 0; i < n; i++) {

current_sum += arr[i];

if (current_sum > max_sum) {

max_sum = current_sum;
start = temp_start;
end = i; }

if (current_sum < 0) {
current_sum = 0;
temp_start = i + 1; }
}

// Print results
printf("Maximum subarray sum: %d\n", max_sum);
printf("Subarray: ");
for (int i = start; i <= end; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}

int main() {
int arr[] = {-2, 11, -4, 13, -5, 2};
int n = sizeof(arr) / sizeof(arr[0]);
 max_subarray_dp(arr, n);

return 0;
}

Output :

Output :
Algorithm 3 :​
Prefix Sum Approach ​
​
​
Algorithm :

●​ Compute Prefix Sum (prefix_sum).

●​ We will Track the min_prefix , start , end indices to determine the best
subarray.
●​ prefix _sum += arr[i] keeps track of cumulative sum .
●​ We will find the maximum subarray by max_sum - min_prefix
●​ We will update the start and end indices when a new max_sum is found.
●​ If prefix_sum is smaller than min_prefix , update min_prefix and adjust
temp_start.

Code : ​
​
#include <stdio.h>
#include <limits.h> // For INT_MIN

void max_subarray_prefix(int arr[], int n) {

int prefix_sum = 0;
int min_prefix = 0;
int max_sum = INT_MIN;
int start = 0, end = 0, temp_start = 0;

for (int i = 0; i < n; i++) {

prefix_sum += arr[i];

if (prefix_sum - min_prefix > max_sum) {

max_sum = prefix_sum - min_prefix;
start = temp_start;
end = i; }

// Update min_prefix and reset temp_start if needed

if (prefix_sum < min_prefix) {
min_prefix = prefix_sum;
temp_start = i + 1;
}
}

// Print results
printf("Maximum subarray sum: %d\n", max_sum);
printf("Subarray with max sum: ");
for (int i = start; i <= end; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {-2, 11, -4, 13, -5, 2};
int n = sizeof(arr) / sizeof(arr[0]);

max_subarray_prefix(arr, n);

return 0;
}

Code

Output :

Time Complexity :

Algorithm Best Case Average Case Worst Case

Kadane’s Algorithm O(n) O(n) O(n)

Dynamic Programming O(n) O(n) O(n)

Prefix Sum Method O(n²) O(n²) O(n²)

Q10 Implement the algorithm (Algo_1) presented below and discuss which task
this algorithm performs. Also, analyze the time complexity and space complexity
of the given algorithm. Further, implement the algorithm with following
modification: replace m = ⌈2n/3⌉ with m = ⌊2n/3⌋, and compare the tasks
performed by the given algorithm and modified algorithm​
​
​
Algo : ​

​
Code:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

// Algorithm 1
void algo(int A[], int l, int r)
{
int n = r - l + 1;
if (n == 2 && A[l] > A[r])
{
int temp = A[l];
A[l] = A[r];
A[r] = temp;
}
else if (n > 2)
{
int m = ceil((2.0 * n) / 3.0);
algo(A, l, l + m - 1);
algo(A, r - m + 1, r);
algo(A, l, l + m - 1);
}
}

// Algorithm 2
void algo2(int A[], int l, int r)
{
int n = r - l + 1;
if (n == 2 && A[l] > A[r])
{
int temp = A[l];
A[l] = A[r];
A[r] = temp;
}
else if (n > 2)
{
int m = floor((2.0 * n) / 3.0);
algo2(A, l, l + m - 1);
algo2(A, r - m + 1, r);
algo2(A, l, l + m - 1);
 }
}

// Function to print an array

void printarray(int A[], int size)
{
for (int i = 0; i < size; i++)
{
printf("%d ", A[i]);
}
printf("\n");
}

int main()
{
int A[] = {5, 3, 8, 1, 4, 7, 2, 6};
int n = sizeof(A) / sizeof(A[0]);

printf("Original array:\n");
printarray(A, n);

// Measure time for algo

int A_copy[n];
for (int i = 0; i < n; i++) A_copy[i] = A[i];

clock_t start = clock();

algo(A_copy, 0, n - 1);
clock_t end = clock();
double time_taken_algo = ((double)(end - start)) / CLOCKS_PER_SEC;

printf("Sorted using algo:\n");

printarray(A_copy, n);
printf("Time taken by algo: %f seconds\n", time_taken_algo);
 // Measure time for algo2
int B[] = {5, 3, 8, 1, 4, 7, 2, 6};

printf("\nOriginal array for algo2:\n");

printarray(B, n);

start = clock();
algo2(B, 0, n - 1);
end = clock();
double time_taken_algo2 = ((double)(end - start)) / CLOCKS_PER_SEC;

printf("Sorted using algo2:\n");

printarray(B, n);
printf("Time taken by algo2: %f seconds\n", time_taken_algo2);

return 0;
}
Output:

Time complexity :
O(n^log₃/₂(3)) = O(n^2.71)
Q 16 Implement MCM algorithm for the given n matrix <M1xM2…​ Mn>
where the size of the matrix is Mi=di-1 x di.​
​
​
Algorithm :

Initialize DP Table:

●​ Create dp[n][n], where dp[i][j] stores the minimum multiplication cost for matrices
Ai to Aj.
●​ Set dp[i][i] = 0 (single matrices require no multiplication).

Iterate Over Chain Lengths (len = 2 to n-1):​

●​ For each i, compute j = i + len - 1.

●​ Initialize dp[i][j] = INT_MAX.

Find Optimal Split Point k:​

●​ Try all k between i and j-1.

●​ Compute cost: cost=dp[i][k]+dp[k+1][j]+(dims[i−1]×dims[k]×dims[j])\text{cost} =
dp[i][k] + dp[k+1][j] + (dims[i-1] \times dims[k] \times
dims[j])cost=dp[i][k]+dp[k+1][j]+(dims[i−1]×dims[k]×dims[j])
●​ Update dp[i][j] with the minimum cost.

Final Result:​

●​ The answer is stored in dp[1][n-1].

Code : #include <stdio.h>

#include <limits.h>
#include <stdlib.h>
#include <time.h>

int matrixChainMult(int dims[], int n) {

int dp[n][n];

for (int i = 1; i < n; i++)

dp[i][i] = 0;

for (int len = 2; len < n; len++) {

for (int i = 1; i < n - len + 1; i++) {
 int j = i + len - 1;
dp[i][j] = INT_MAX;
for (int k = i; k < j; k++) {
int cost = dp[i][k] + dp[k+1][j] + dims[i-1] * dims[k] * dims[j];
if (cost < dp[i][j])
dp[i][j] = cost;
}
}
}
return dp[1][n-1];
}

int matrixMult(int dims[], int n) {

int cost = 0;
for (int i = 1; i < n - 1; i++) {
cost += dims[0] * dims[i] * dims[i + 1];
}
return cost;
}

int main() {
srand(time(0));

int d = (rand() % 10) + 2;

int dims[d];

for (int i = 0; i < d; i++) {

dims[i] = (rand() % 20) + 1;
}

printf("Array of dimensions: ");

for (int i = 0; i < d; i++) {
printf("%d ", dims[i]);
}
printf("\n");

int n = d;
printf("number of multiplications by dp : %d\n", matrixChainMult(dims, n));
printf("Naive multiplications: %d\n", matrixMult(dims, n));

return 0;
}

output:
Time Complexity: O(n³)
Space Complexity: O(n²)