Question

Objective:This assignment is designed to give you experience with thinking about algorithm analysis and performanceevaluation.Project DescriptionYou will analyze three algorithms to solve the maximum contiguous subsequence sum problem, and then evaluate the performance of instructor-supplied implementations of those three algorithms. You will compare your theoretical results to your actual results in a written report.What is the maximum contiguous subsequence sum problem?Given a sequence of integers A1, A2 ... An (where the integers may be positive or negative), find a subsequence Aj, ..., Ak that has the maximum value of all possible subsequences.The maximum contiguous subsequence sum is defined to be zero if all of the integers in the sequence are negative.

Answer 1

Answer:

Check the explanation

Explanation:

#include<stdio.h>

/*Function to return max sum such that no two elements

are adjacent */

int FindMaxSum(int arr[], int n)

{

 int incl = arr[0];

 int excl = 0;

 int excl_new;

 int i;

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

 {

    /* current max excluding i */

    excl_new = (incl > excl)? incl: excl;

    /* current max including i */

    incl = excl + arr[i];

    excl = excl_new;

 }

  /* return max of incl and excl */

  return ((incl > excl)? incl : excl);

}

/* Driver program to test above function */

int main()

{

 int arr[] = {5, 5, 10, 100, 10, 5};

 printf("%d \n", FindMaxSum(arr, 6));

 getchar();

 return 0;

}