C Exercises: Maximum sum of a contiguous subsequence from a given sequence of numbers

C Basic Declarations and Expressions: Exercise-139 with Solution

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 Code Editor:

Previous: Write a C program to test whether two lines are parallel or not. The four points are P(x1, y1), Q(x2, y2), R(x3, y3) and S(x4, y4), check PQ and RS are parallel are not.
Next: Write a C program to which reads a sequence of integers and find the element which occurs most frequently.