討論串[問題] 連續整數相乘，求乘積最大?
共 6 篇文章
內容預覽:
遞迴式給你, 如果看不懂可能得回去翻翻 dynamic programming 那一章了 :P. 令 a(i) 為第 i 個數字, i = 1 ~ n. P(i) 為結束在 a(i) 的連續數列中, 最大正值乘積. 可為零. 如果不存在, 記作 Orz. N(i) 為結束在 a(i) 的連續數列中,
(還有507個字)
內容預覽:
這方法比較笨而且慢. 關鍵在於開始乘的起點. 比如 0 0 1 2 3 -1 3 4 5 -2 1 來說好了. 一開始begin當然是0. 1.如果乘數為0 begin加1. 2.如果乘數是正數 begin加1 並標明begin更動過. 3.如果乘數是負數. 第一次碰到負數. 將之前的乘積丟到vec
(還有2300個字)
內容預覽:
科科 給你一個 簡單 又 快 (好像在那裡也講過!?) 的演算法. O(n^2) ( 不知道有沒有可能可以降到O(n) ). #include <stdlib.h>. #include <stdio.h>. int array[]={0,0,1,2,3,-1,3,4,5,-2,1}; //從這裡輸入
(還有530個字)
內容預覽:
上面的都對. 不過在這問題裡有個很重要的地方. 那就是. 不看正負號的話, 整數都是越乘越大!!!. 所以大略是. 只要簡單找一段偶數個負號. 然後讓這段越長就越好. 不考慮一些boundary condition. 只提大概. 方法如下. 看到0就切斷 O(n). 所以現在有一段段沒有0的. 對於
(還有71個字)