Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1004071
  • 博文数量: 150
  • 博客积分: 3017
  • 博客等级: 少校
  • 技术积分: 3829
  • 用 户 组: 普通用户
  • 注册时间: 2011-11-19 14:40
个人简介

Now in Baidu WISE team

文章分类

全部博文(150)

文章存档

2014年(8)

2013年(31)

2012年(111)

分类: C/C++

2012-12-30 15:59:33

求给定数组中的连续子数组的最大乘积。
 
简单DP,练手。codepad.org已验证

点击(此处)折叠或打开

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <memory.h>
  4. #define MAX 1000

  5. int getmaxsub(int *input, int size){
  6.     if(input == NULL || size == 0) return 0xFFFF;
  7.     if(size == 1) return input[0];
  8.     int cur[size];
  9.     int next[size];
  10.     memcpy(cur, input, sizeof(int)*size);
  11.     int maxmult = -MAX;
  12.     int len = 1;
  13.     for(;len<size;len++){
  14.         int end = len;
  15.         for(;end<size;end++){
  16.             next[end] = cur[end-1] * input[end];
  17.             if(next[end]>maxmult){
  18.                 maxmult = next[end];
  19.             }
  20.         }
  21.         memcpy(cur,next,sizeof(int)*size);
  22.     }
  23.     return maxmult;
  24. }

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

阅读(2542) | 评论(1) | 转发(1) |
给主人留下些什么吧!~~

sslss20122013-03-24 13:44:47

你的方法有问题
例如 3,5,2,0,4,2,15   输出为30 
     0,3,5,2          输出为15