Note that when all the numbers are positive, the entire array gives the maximum
ID: 3555653 • Letter: N
Question
Note that when all the numbers are positive, the entire array gives the maximum sum, and when all of the elements are negative, then the empty array maximizes the sum at 0.
a) Give a simple, clear and correct O(n^2)- time algorithm to find the maximun contiguous subvector.
b) Give an O(n)-time dynamic programming algorithm.
Given an array of real numbers with length n, it is sometimes useful to compute the maximum sum of any contiguous subvector of the array. For example, consider the following array:Explanation / Answer
A) O(n^2)
#include<stdio.h>
int maxSubArraySum(int a[], int size)
{
int max_so_far = 0, max_ending_here = 0;
int i;
for(i = 0; i < size; i++)
{
max_ending_here = max_ending_here + a[i];
if(max_ending_here < 0)
max_ending_here = 0;
if(max_so_far < max_ending_here)
max_so_far = max_ending_here;
}
return max_so_far;
}
/*Driver program to test maxSubArraySum*/
int main()
{
int a[] = {31, -41, 59, 26, -53, 58, 97, -93, -23, 84};
int n = sizeof(a)/sizeof(a[0]);
int max_sum = maxSubArraySum(a, n);
printf("Maximum contiguous sum is %d ", max_sum);
getchar();
return 0;
}
b) O(n)
#include<stdio.h>
int max(int x, int y)
{ return (y > x)? y : x; }
int maxSubArraySum(int a[], int size)
{
int max_so_far = a[0], i;
int curr_max = a[0];
for (i = 1; i < size; i++)
{
curr_max = max(a[i], curr_max+a[i]);
max_so_far = max(max_so_far, curr_max);
}
return max_so_far;
}
/* Driver program to test maxSubArraySum */
int main()
{
int a[] = {31, -41, 59, 26, -53, 58, 97, -93, -23, 84};
int n = sizeof(a)/sizeof(a[0]);
int max_sum = maxSubArraySum(a, n);
printf("Maximum contiguous sum is %d ", max_sum);
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.