fork download
copy 
  1. /* subsequence with maximal sum, computed in linear time */
  2.  
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5.  
  6. /** 
  7.  *  compute the subsequece with maximal sum
  8.  *  @param[in] a the whole sequence 
  9.  *  @param[in] n number of elements in the sequence
  10.  *  @param[out] st starting index of the subsequence
  11.  *  @param[out] len number of elements in the subsequence
  12.  *  @return the maximal sum
  13.  */
  14. int maxSumLinTime (int *a, int n, int *st, int *len) {
  15.   int maxSum = 0, sum = 0, i, s = 0;
  16.   *st = -1, *len = 0;
  17.   for (i = 0; i < n; i ++) {
  18.     sum += a[i];
  19.     if (sum > maxSum) {
  20.       maxSum = sum;
  21.       *st = s;
  22.       *len = i - s + 1;
  23.     }
  24.     if (sum < 0) {
  25.       sum = 0;
  26.       s = i + 1;
  27.     }
  28.   }
  29.   return maxSum;
  30. }
  31.  
  32. int main(void) {
  33.   int a[] = { 1, -3, 4, -2, -1, 6, -8, 3, 1, 1 }, /* a[2] + a[3] + a[4] + a[5] = 7 */
  34.       st, len;
  35.   int sum = maxSumLinTime(a, sizeof(a)/sizeof(int), &st, &len);
  36.   printf("start of subsequence: %d, length of subsequence: %d, max. sum: %d\n",
  37.          st, len, sum);
  38.   return EXIT_SUCCESS;
  39. }
  40.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
start of subsequence: 2, length of subsequence: 4, max. sum: 7
https://ideone.com/3wvaIp
language:
C++14 (gcc 8.3)
created:
16 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!