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;
  printf("Input number of terms in the sequence:\n");
  scanf("%d", & n);
  printf("\nInput the terms of the said sequence:\n");
  for (i = 0; i < n; i++) scanf("%ld", & (a[i]));

  max = a[0];
  tmp = 0;

  for (i = 0; i < n; i++) {
    for (j = i; j < n; j++) {
      tmp += a[j];
      if (max < tmp)
        max = tmp;
    }
    tmp = 0;
  }
  printf("Maximum sum of a contiguous subsequence:\n");
  printf("%lld\n", max);
  return 0;
}

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:

Contribute your code and comments through Disqus.

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.