作者netsphere (我需要人陪我)
看板Prob_Solve
标题Re: [问题] 连续整数相乘，求乘积最大?
时间Fri May 16 15:37:00 2008
科科 给你一个 简单 又 快 (好像在那里也讲过!?) 的演算法
O(n^2) ( 不知道有没有可能可以降到O(n) )
#include <stdlib.h>
#include <stdio.h>
int array[]={0,0,1,2,3,-1,3,4,5,-2,1}; //从这里输入
int rx,ry,max=0,pr,nx;
int main()
{
for (int r = 0; r < (sizeof(array)/4-1) ; r++ )
{
pr=array[r];
for (int k = r+1 ; k <= (sizeof(array)/4-1) ; k++)
{
nx = pr* array[k];
pr=nx;
if (nx > max)
{
max=nx;
rx = r;
ry = k;
}
}
}
for (int d = rx;d<ry;d++)
{
printf("%4d *",array[d]);
}
printf("%4d = %4d\n",array[ry],max);
system("PAUSE");
return 0;
}
--
netsphere:我想到一个字串比对的方法
众:.......
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 218.165.195.81
※ 编辑: netsphere 来自: 218.165.195.81 (05/16 15:38)
1F：→ bleed1979:如果输入1 0 跑出的答案为0 应该要为1才对 05/16 16:21
2F：推 march20:对喔, 这题其实只要暴力就解得出来了 XD 05/16 17:03
3F：推 march20:居然忘了 "想最佳解前, 记得先试暴力法" 这件事 :P 05/16 17:05
4F：→ netsphere:其实 这是从DP改过来的拉 XD 纯暴力法要O(N^3) 05/16 17:28
5F：→ netsphere:有点小BUG 不过概念大概就是这样 ...还有 版主好 (惊) 05/16 17:30