最近脑袋发木,找一些脑筋急转弯的题目来写写。

题目:有一个整数数组,求其连续子数组的最大和。

#include <stdio.h>
#include <strings.h>
#include <math.h>

#define MAXLEN 1024

int arr[MAXLEN], num=0;

int read2arr(){
        bzero(arr, MAXLEN * sizeof(int));
        int *p=arr;

        while(!feof(stdin)){
                if(++num > MAXLEN){
                        fprintf(stderr, "Too many numbers!");
                        return -1;
                }
                scanf("%d", p++);
        }
        num--;

        /*
        for(p=arr; p<arr+num; ++p){
                printf("%d\n", *p);
        }
        */
        return 0;
}

long maxsum(){
        long max = (long)-pow(2,31), sum=0;
        int i = 0;

        for(;i<num;++i){
                if(sum + arr[i] > 0){
                        sum += arr[i];

                        if (sum > max){
                                max = sum;
                        }
                } else{
                        sum = 0;
                }
        }

        return max;
}

int main(int argc, char** argv){
        if(read2arr() < 0){
                return -1;
        }

        printf("max child sum: %ld\n", maxsum());

        return 0;
}


思路是,依次遍历数组时,如果前面累积的和为负数或0,则只会使后面的数之和变小,所以可以抛弃。

Leave a Reply