连续乘积最大子数组

求给定数组中的连续子数组的最大乘积。

 

简单DP,练手。codepad.org已验证

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#define MAX 1000

int getmaxsub(int *input, int size){
    if(input == NULL || size == 0) return 0xFFFF;
    if(size == 1) return input[0];
    int cur[size];
    int next[size];
    memcpy(cur, input, sizeof(int)*size);
    int maxmult = -MAX;
    int len = 1;
    for(;len<size;len++){
        int end = len;
        for(;end<size;end++){
            next[end] = cur[end-1] * input[end];
            if(next[end]>maxmult){
                maxmult = next[end];
            }
        }
        memcpy(cur,next,sizeof(int)*size);
    }
    return maxmult;
}

int main(){
    int input[] = {5,3,2,4,-9,1};
    printf("max mult : %d \n", getmaxsub(input,6));
}