Re: [問題] 連續整數相乘，求乘積最大?

[netsphere (我需要人陪我)]

科科 給你一個 簡單 又 快 (好像在那裡也講過!?) 的演算法

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)
→ bleed1979:如果輸入1 0  跑出的答案為0　應該要為1才對
推 march20:對喔, 這題其實只要暴力就解得出來了 XD
推 march20:居然忘了 "想最佳解前, 記得先試暴力法" 這件事 :P
→ netsphere:其實 這是從DP改過來的拉  XD  純暴力法要O(N^3)
→ netsphere:有點小BUG 不過概念大概就是這樣   ...還有 版主好 (驚)