so true

#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>
#include <string>
#include <fstream>
#include <sstream>
#include <stdint.h>
#include <pthread.h>
#include <vector>
#include <map>
#include <set>

using namespace std;

void print_array(int* ary, int len) {
    for (int i = 0; i < len; ++i) {
        if (0 == i) {
            printf("%3d", ary[i]);
        } else {
            printf(" %3d", ary[i]);
        }
    }
    printf("\n");
}

int calc_max_sum2(int* ary, int len) {
    int max_ele = 1 << (8 * sizeof(int) - 1);
    int max_ele_pos = -1;
    int max = 0;

    int sum = 0;
    int start_pos = 0;
    int max_end_pos = -1;
    int max_start_pos = -1;
    for (int i = 0; i < len; ++i) {
        if (ary[i] > max_ele) {
            max_ele = ary[i];
            max_ele_pos = i;
        }
        sum += ary[i];
        if (sum < 0) {
            sum = 0;
            if (i + 1 < len) {
                start_pos = i + 1;
            }
        } else if (sum > max) {
            max = sum;
            max_end_pos = i;
            max_start_pos = start_pos;
        }
    }

    if (max_ele < 0) {
        max = max_ele;
        max_start_pos = max_ele_pos;
        max_end_pos = max_ele_pos;
    }

    printf("algorithm 2: max subsequence starts from %d, length:%d, max result:%d\n", max_start_pos, max_end_pos - max_start_pos + 1, max);
    print_array(ary + max_start_pos, max_end_pos - max_start_pos + 1);

    return max;
}

int calc_max_sum1(int* ary, int len) {
    if (NULL == ary || 0 == len) {
        return 0;
    }

    int max_ele = 1 << (8 * sizeof(int) - 1);
    int max_ele_pos = -1;

    int max_sum = 0;
    int max_start_pos = -1;
    int max_end_pos = -1;

    int cur_sum = 0; //reserve the optimal state
    int start_pos = -1; //record the start pos for cur_sum
    int end_pos = -1;//record the end pos for cur_sum
    int part_sum = 0; //track the incremental part, and merge into cur_sum once it is positive
    for (int i = 0; i < len; ++i) {
        if (ary[i] > max_ele) {
            max_ele = ary[i];
            max_ele_pos = i;
        }
        part_sum += ary[i];
        if (part_sum < 0) {
            if (cur_sum + part_sum < 0) {
                if (cur_sum > max_sum) {
                    max_sum = cur_sum;
                    max_start_pos = start_pos;
                    max_end_pos = end_pos;
                }

                cur_sum = 0;
                start_pos = -1;
                end_pos = -1;
                part_sum = 0;
            }
        } else if (part_sum > 0) {
            cur_sum += part_sum;
            part_sum = 0;
            end_pos = i;
            if (-1 == start_pos) {
                start_pos = i;
            }
        }
        //printf("%3d, cur_sum:%3d, start_pos:%3d, end_pos:%3d, part_sum:%3d, max_sum:%3d, max_start_pos:%3d, max_end_pos:%3d\n", i, cur_sum, start_pos, end_pos, part_sum, max_sum, max_start_pos, max_end_pos);
    }
    if (cur_sum > max_sum) {
        max_sum = cur_sum;
        max_start_pos = start_pos;
        max_end_pos = end_pos;
    }

    if (max_ele < 0) {
        max_sum = max_ele;
        max_start_pos = max_ele_pos;
        max_end_pos = max_ele_pos;
    }

    printf("algorithm 1: max subsequence starts from %d, length:%d, max result:%d\n", max_start_pos, max_end_pos - max_start_pos + 1, max_sum);
    print_array(ary + max_start_pos, max_end_pos - max_start_pos + 1);

    return max_sum;
}

int calc_sum(int* ary, int len) {
    int sum = 0;
    for (int i = 0; i < len; ++i) {
        sum += ary[i];
    }

    return sum;
}

int calc_max_sum_by_enumerate(int* ary, int len) {
    int max = 1 << (8 * sizeof(int) - 1);
    int begin = -1;
    int max_len = -1;
    for (int i = 0; i < len; ++i) {
        for (int j = i; j < len; ++j) {
            int sum = calc_sum(ary + i, j - i + 1);
            if (sum > max) {
                max = sum;
                begin = i;
                max_len = j - i + 1;
            }
        }
    }

    printf("algorithm of enumerate: max subsequence starts from %d, length:%d, max result:%d\n", begin, max_len, max);
    print_array(ary + begin, max_len);

    return max;
}

int main(int argc, char* argv[]) {
    int* ary = NULL;
    int len = 0;
    if (argc > 2) {
        len = argc - 1;
        ary = new int[len];
        for (int i = 1; i < argc; ++i) {
            ary[i - 1] = atoi(argv[i]);
        }
    } else if (2 == argc) {
        len = atoi(argv[1]);
        ary = new int[len];
        struct timeval tv;
        gettimeofday(&tv, NULL);
        srandom(tv.tv_usec);
        for (int i = 0; i < len; ++i) {
            ary[i] = (random() % 20) - 10;
        }
    } else {
        int tmp_ary[] = {-4, 6, -5, 3, -3, 4, -2};
        len = sizeof(tmp_ary) / sizeof(tmp_ary[0]);
        ary = new int[len];
        memcpy(ary, tmp_ary, sizeof(tmp_ary));
    }
    print_array(ary, len);
    int ret1 = calc_max_sum1(ary, len);
    int ret2 = calc_max_sum2(ary, len);
    int max = calc_max_sum_by_enumerate(ary, len);
    if (ret1 != max) {
        printf("algorithm 1 fails, result is %d, but the right answer is %d\n", ret1, max);
    } else if (ret2 != max) {
        printf("algorithm 2 fails, result is %d, but the right answer is %d\n", ret2, max);
    } else {
        printf("algorithm succeeds, max result:%d\n", max);
    }

    delete [] ary;
    return 0;
}