<Cracking the Coding Interview>--제17장: 일반문제--제목8

2014-04-28 23:35
제목: 가장 큰 하위 그룹과 문제.
해법: O(n) 해법.
코드:

 1 // 17.8 Find the consecutive subarray with maximum sum in an array.

 2 // O(n) online algorithm.

 3 #include <cstdio>

 4 #include <vector>

 5 using namespace std;

 6 

 7 int maximumSum(vector<int> &v)

 8 {

 9     int n = (int)v.size();

10     

11     if (n == 0) {

12         return 0;

13     }

14     

15     int val = v[0];

16     int i;

17     

18     for (i = 1; i < n; ++i) {

19         val = val > v[i] ? val : v[i];

20     }

21     

22     if (val <= 0) {

23         return val;

24     }

25     

26     int res;

27     res = val = 0;

28     for (i = 0; i < n; ++i) {

29         val += v[i];

30         if (val > res) {

31             res = val;

32         }

33         if (val < 0) {

34             val = 0;

35         }

36     }

37     

38     return res;

39 }

40 

41 int main()

42 {

43     vector<int> v;

44     int n, i;

45     

46     while (scanf("%d", &n) == 1 && n > 0) {

47         v.resize(n);

48         for (i = 0; i < n; ++i) {

49             scanf("%d", &v[i]);

50         }

51         printf("%d
", maximumSum(v));

52         v.clear();

53     }

54     

55     return 0;

56 }