FilesExpand file tree

 master

/

max_subsequence_sum.c

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

21 lines (19 loc) · 491 Bytes

 master

/

max_subsequence_sum.c

Copy path

Top

File metadata and controls

• Code
• Blame

21 lines (19 loc) · 491 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

/* max_subsequence_sum: compute max subsequence sum of a[n]

on-lines algorithms; O(n) */

int max_subsequence_sum(int a[], unsigned n) {

int this_sum, max_sum, best_i, best_j, i, j;

i = this_sum = max_sum = 0; best_i = best_j = -1;

for (j = 0; j < n; j++) {

this_sum += a[j];

if (this_sum > max_sum)

{ /* update max_sum, best_i, best_j */

max_sum = this_sum;

best_i = i;

best_j = j;

} else if (this_sum < 0) {

i = j + 1;

this_sum = 0;

}

}

return max_sum;

}