微软面试100题(3):求连续子数组的最大和

3.求子数组的最大和
题目：
输入一个整形数组，数组里有正数也有负数。

数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。

例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，
因此输出为该子数组的和18。

这是个简单的动态规划题。结果用一维数组表示即可。

设第n个数,包含n的和最大的连续子数组的和是f(n),

那么对于前n+1个数来说，包含第n+1个数（即n+1是子数组的最后一个元素），最大连续子数组和，要么为 n+1,要么为f(n）+n+1

即f(n+1) = max(f(n)+input[n+1], input[n+1]);

/*
 * =====================================================================================
 *
 *       Filename:  maxsum.c
 *
 *    Description:
 *
 *        Version:  1.0
 *        Created:  10/02/2012 10:13:50 PM
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  YOUR NAME (),
 *   Organization:
 *
 * =====================================================================================
 */
#include <stdlib.h>
#include <stdio.h>

int input[] = {1, -2, 3, 10, -4, 7, 2, -5};
int result[sizeof(input)/sizeof(int)];
int max = 0;

void run(){
    result[0] = input[0];
    int i = 1;
    for(;i<sizeof(input)/sizeof(int);i++){
        result[i] = (result[i-1] + input[i]) >input[i] ? (result[i-1] + input[i]):input[i];
        max = max>result[i]?max:result[i];
    }
}

/*
 * ===  FUNCTION  ======================================================================
 *         Name:  main
 *  Description:
 * =====================================================================================
 */
    int
main ( int argc, char *argv[] )
{
    run();
    printf ( "max sum: %d\n",max );
    return EXIT_SUCCESS;
}                /* ----------  end of function main  ---------- */