w3resource

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:

C Programming Flowchart: Maximum sum of a contiguous subsequence from a given sequence of numbers.


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.



Follow us on Facebook and Twitter for latest update.