C Exercises: Maximum sum of a contiguous subsequence from a given sequence of numbers
Maximum sum of a contiguous subsequence in an array
Write a C program to find the maximum sum of a contiguous subsequence from a given sequence of numbers a1, a2, a3, ... an ( n = number of terms in the sequence).
You can assume that 1 <= n <= 500 and -10000 <= ai <= 10000.
A contiguous subsequence of a list S is a subsequence made up of consecutive elements of S.
For instance, if S is
5, 15, −30, 10, −5, 40, 10,
then 15, −30, 10 is a contiguous subsequence but 5, 15, 40 is not.
Give a linear-time algorithm for the following task:
• Input: A list of numbers a1, a2, . . . , an
• Output: The contiguous subsequence of maximum sum. (Note that a subsequence of
length zero has sum zero.)
For the preceding example, the answer would be 10, −5, 40, 10, with a sum of 55
Ref: https://bit.ly/2IGGI3f
Sample Solution:
C Code:
#include <stdio.h>
int main() {
int n;
long a[5000];
long long max, tmp;
int i, j;
// Getting the number of terms in the sequence from the user
printf("Input number of terms in the sequence:\n");
scanf("%d", &n);
// Getting the terms of the sequence from the user
printf("\nInput the terms of the said sequence:\n");
for (i = 0; i < n; i++)
scanf("%ld", &(a[i]));
max = a[0];
tmp = 0;
// Finding the maximum sum of a contiguous subsequence
for (i = 0; i < n; i++) {
for (j = i; j < n; j++) {
tmp += a[j];
if (max < tmp)
max = tmp;
}
tmp = 0;
}
// Printing the maximum sum of a contiguous subsequence
printf("Maximum sum of a contiguous subsequence:\n");
printf("%lld\n", max);
return 0; // End of the program
}
Sample Output:
Input number of terms in the sequence: 5 Input the terms of the said sequence: 3 2 6 -7 8 Maximum sum of a contiguous subsequence: 12
Flowchart:
For more Practice: Solve these Related Problems:
- Write a C program to implement Kadane’s algorithm to find the maximum contiguous subsequence sum in an array.
- Write a C program to compute the maximum sum subsequence using dynamic programming with an iterative loop.
- Write a C program to find and print the subarray corresponding to the maximum sum using pointer manipulation.
- Write a C program to use recursion and memoization to determine the maximum sum of any contiguous subsequence.
Go to:
PREV : Determine if two lines are parallel.
NEXT : Find the most frequently occurring number in a sequence.
C programming Code Editor:
What is the difficulty level of this exercise?
Test your Programming skills with w3resource's quiz.