青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

Dain

寫出一個可以工作的程序并不夠

統計

留言簿(3)

積分與排名

良師益友

閱讀排行榜

評論排行榜

最大的子序列和問題

求解該問題的四種算法:
時間O(N3),算法一
int ?MaxSubsequenceSum( const ? int ?A[], int ?N)
{
????
int
?ThisSum,MaxSum,i,j,k;
????
????MaxSum?
= ? 0
;
????
for (i? = ? 0 ;i? < ?N;i ++
)
????????
for (j? = ?i;j? < ?N;j ++
)
????????
{
????????????ThisSum?
= ? 0
;
????????????
for (k? = ?i;k? <= ?j;k ++ )????ThisSum? +=
?A[k];????????????????
????????????
if (ThisSum? > ?MaxSum)????MaxSum? =
?ThisSum;
????????}

????????
????
return ?MaxSum;
}
時間O(N2),算法二
int ?MaxSubsequenceSum( const ? int ?A[], int ?N)
{
????
int
?ThisSum,MaxSum,i,j;
????
????MaxSum?
= ? 0
;
????
for (i? = ? 0 ;i? < ?N;i ++
)
????
{
????????ThisSum?
= ? 0
;
????????
for (j? = ?i;j? < ?N;j ++
)
????????
{
????????????ThisSum?
+=
?A[k];????????????????
????????????
if (ThisSum? > ?MaxSum)????MaxSum? =
?ThisSum;
????????}

????}

????????
????
return ?MaxSum;
}
時間O(NlogN),算法三
static ? int ?MaxSubSum( const ? int ?A[], int ?Left, int ?Right)
{
????
int
?MaxLeftSum,MaxRightSum;
????
int
?MaxLeftBorderSum,MaxRightBorderSum;
????
int
?LeftBorderSum,RightBorderSum;
????
int
?Center,i;
????
????
if (Left? ==
?Right)
????????
if (A[left]? > ? 0 )???? return
?A[left];
????????
else ???? return ? 0
;
????????????
????Center?
= ?(Left? + ?Right)? / ? 2
;
????MaxLeftSum?
=
?MaxSubSum(A,Left,Center);
????MaxRightSum?
= ?MaxSubSum(A,Center? + ? 1
,Right);
????
????MaxLeftBorderSum?
= ? 0
;
????LeftBorderSum?
= ? 0
;
????
for (i? = ?Center;i? >= ?Left;i --
)
????
{
????????LeftBorderSum?
+=
?A[i];
????????
if (LeftBorderSum? > ?MaxLeftBorderSum)????MaxLeftBorderSum? =
?LeftBorderSum;
????}

????
????MaxRightBorderSum?
= ? 0 ;
????RightBorderSum?
= ? 0
;
????
for (i? = ?Center? + ? 1 ;i? <= ?Right;i ++
)
????
{
????????RightBorderSum?
+=
?A[i];
????????
if (RightBorderSum? > ?MaxRightBorderSum)????MaxRightBorderSum? =
?RightBorderSum;
????}

????
????
return ?Max3(MaxLeftSum,MaxRightSum,MaxLeftBorderSum? + ?MaxRightBorderSum);
}


int ?MaxSubsequenceSum( const int??A[],int ?N)
{
????
return ?MaxSubSum(A, 0 ,N? - ? 1
);????
}
時間O(N),算法四
intMaxSubsequenceSum( const int ?A[], int ?N)
{
????
int ?ThisSum,MaxSum,i;
????
????ThisSum?
= ?MaxSum? = ? 0 ;
????
for (i? = ? 0 ;i? < ?N;i ++ )
????
{
????????ThisSum?
+= ?A[i];
????????
if (ThisSum? > ?MaxSum)
????????????MaxSum?
= ?ThisSum;
????????
else
????????????ThisSum?
= ? 0 ;
????}

????
????
return ?MaxSum;
}


參考《數據結構與算法分析》

posted on 2007-02-07 10:52 Dain 閱讀(1093) 評論(7)  編輯 收藏 引用 所屬分類: 算法筆記

評論

# re: 最大的子序列和問題[未登錄] 2007-02-08 01:36

呵呵, dp是王道  回復  更多評論   

# re: 最大的子序列和問題 2007-02-08 16:53 Dain

嗯,dp
對于這個問題,算法三和四都是不錯的思路@豪
  回復  更多評論   

# re: 最大的子序列和問題 2007-02-09 16:24 alai04

樓主開什么玩笑,算法四明顯是不對的嘛,是考一下我們的眼力嗎?  回復  更多評論   

# re: 最大的子序列和問題 2007-03-25 20:50 felix

四不對
如:
1 5 -3 2 4
  回復  更多評論   

# re: 最大的子序列和問題 2007-03-25 20:51 felix

三用的是分治,不是DP吧?  回復  更多評論   

# re: 最大的子序列和問題 2007-03-30 11:12 dqchen

第四個
MaxSum = -((static_cast<unsigned int>(~0)) >> 1) - 1;

ThisSum = 0;
for (int i = 0;i < A.size();i++)
{
ThisSum += A[i];
if(ThisSum > MaxSum)
MaxSum = ThisSum;
else
ThisSum = 0;
}
  回復  更多評論   

# 第四個算法的實現是錯誤的 2008-07-04 17:53 wetwoo

輸入如下:-2 11 -4 13 -5 -2
輸出如下:13
正確輸出應該為:20
修改如下:
intMaxSubsequenceSum( const int A[], int N)
{
int ThisSum,MaxSum,i;

ThisSum = MaxSum = 0 ;
for (i = 0 ;i < N;i ++ )
{
ThisSum += A[i];
if (ThisSum > MaxSum)
MaxSum = ThisSum;
else if(ThisSum < 0)
ThisSum = 0 ;
}

return MaxSum;
}   回復  更多評論   

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            亚洲激情在线观看| 国产精品视频内| 亚洲一区二区三区在线播放| 亚洲精品免费在线播放| 欧美激情片在线观看| 亚洲精品女av网站| 亚洲精选在线观看| 亚洲一区国产视频| 性欧美video另类hd性玩具| 欧美一区网站| 欧美电影免费观看网站| 欧美特黄a级高清免费大片a级| 国产精品久久久久一区二区三区共 | 免费成年人欧美视频| 欧美大成色www永久网站婷| 欧美精品亚洲精品| 国产精品永久免费在线| 亚洲国产一区二区精品专区| 亚洲网站在线看| 美日韩精品免费| 夜夜嗨一区二区| 欧美综合国产| 国产精品不卡在线| 最近中文字幕mv在线一区二区三区四区| 正在播放亚洲一区| 久久国产天堂福利天堂| 亚洲黄色在线观看| 久久精品人人做人人综合| 欧美日韩高清在线观看| 国产一区香蕉久久| 亚洲一区二区精品在线| 亚洲国产日韩欧美综合久久| 久久嫩草精品久久久精品| 欧美日韩成人激情| 国模精品一区二区三区| 亚洲伊人久久综合| 亚洲第一偷拍| 欧美自拍偷拍| 国产精品爽黄69| 99亚洲伊人久久精品影院红桃| 久久精品国产2020观看福利| 亚洲精品在线看| 欧美阿v一级看视频| 一区二区三区在线观看视频| 欧美一区二区三区精品电影| 一本色道久久综合亚洲精品不| 免费看亚洲片| 亚洲国产成人在线视频| 久久综合伊人77777尤物| 性欧美暴力猛交另类hd| 国产农村妇女精品一二区| 亚洲欧美清纯在线制服| 一区二区精品在线| 欧美欧美天天天天操| 亚洲美女一区| 亚洲日本无吗高清不卡| 欧美激情小视频| 99国产精品99久久久久久粉嫩| 亚洲二区视频在线| 牛牛影视久久网| 亚洲人屁股眼子交8| 欧美激情片在线观看| 欧美成人激情在线| 99视频+国产日韩欧美| 亚洲精品色婷婷福利天堂| 欧美精品一区二区三区蜜臀| 99在线视频精品| 一区二区日韩精品| 国产精品久久77777| 篠田优中文在线播放第一区| 亚洲视频免费看| 国产精品综合| 久久精品91| 久久综合伊人77777| 亚洲欧洲日本国产| 亚洲裸体俱乐部裸体舞表演av| 欧美色精品在线视频| 欧美淫片网站| 麻豆九一精品爱看视频在线观看免费| 亚洲美女在线视频| 亚洲一区在线观看视频| 狠狠色综合日日| 亚洲国产影院| 国产精品天天看| 欧美高清在线播放| 欧美亚韩一区| 美女日韩欧美| 久久一区中文字幕| 黑人中文字幕一区二区三区 | 亚洲欧美日韩在线观看a三区| 久久色在线播放| 亚洲精品久久嫩草网站秘色| 亚洲精品日韩一| 国产在线精品成人一区二区三区 | 国产专区精品视频| 亚洲国内精品在线| 国产伦精品一区二区三区高清版| 久久久久一区| 欧美日韩免费一区| 麻豆国产精品va在线观看不卡| 欧美巨乳波霸| 久久久久久亚洲精品杨幂换脸| 欧美国产一区二区| 欧美呦呦网站| 欧美日韩国产免费| 久久噜噜噜精品国产亚洲综合| 欧美绝品在线观看成人午夜影视 | 一区二区av| 久久青草久久| 欧美伊人久久| 欧美性色综合| 亚洲三级免费电影| 亚洲激情黄色| 久久天天躁狠狠躁夜夜爽蜜月| 亚洲综合精品四区| 欧美国产欧美综合| 欧美成人蜜桃| 极品少妇一区二区| 午夜免费电影一区在线观看| 亚洲天堂激情| 欧美四级剧情无删版影片| 欧美黄色日本| 激情视频一区二区三区| 午夜一区在线| 欧美制服丝袜第一页| 国产精品a久久久久久| 91久久夜色精品国产网站| 亚洲国产欧美日韩精品| 久久久之久亚州精品露出| 久久久久久久国产| 国产亚洲欧美aaaa| 香蕉久久精品日日躁夜夜躁| 亚洲欧美卡通另类91av| 国产精品v一区二区三区| 亚洲久久在线| 亚洲天堂激情| 国产精品久久中文| 亚洲欧美国产日韩中文字幕| 亚洲欧美日韩精品久久奇米色影视| 欧美日韩中文字幕在线视频| 亚洲伦理精品| 亚洲欧美一区二区视频| 国产精品视频观看| 午夜精品一区二区三区四区| 久久激情视频久久| 一区免费视频| 欧美成va人片在线观看| 亚洲人成人一区二区三区| 亚洲精品精选| 欧美午夜精品| 久久精品二区三区| 欧美顶级大胆免费视频| 亚洲午夜伦理| 国内精品久久久久久久97牛牛| 亚洲精品少妇| 久久成人在线| 欧美成人首页| 亚洲视频免费在线| 国产麻豆精品视频| 麻豆国产精品va在线观看不卡| 欧美激情综合色| 中日韩午夜理伦电影免费| 国产精品日日摸夜夜添夜夜av| 欧美专区在线| 亚洲狠狠婷婷| 欧美一区二区三区电影在线观看| 国产在线播放一区二区三区| 欧美二区不卡| 午夜精品久久久99热福利| 欧美激情第六页| 欧美影视一区| 在线亚洲美日韩| 在线观看国产精品网站| 欧美性猛交视频| 久久蜜桃精品| 亚洲一级特黄| 亚洲国产欧美一区二区三区久久| 亚洲欧美网站| 亚洲精品国产品国语在线app| 国产精品日韩欧美| 欧美mv日韩mv国产网站| 亚洲免费视频网站| 亚洲精品系列| 农夫在线精品视频免费观看| 亚洲欧美大片| av成人动漫| 亚洲国产成人久久综合| 国产日韩欧美高清| 欧美性猛交99久久久久99按摩| 美女日韩欧美| 久久久久国产成人精品亚洲午夜| 在线亚洲自拍| 99riav1国产精品视频| 亚洲大片在线| 欧美69wwwcom| 美日韩精品免费观看视频| 久久久久久久高潮| 久久久久久久久久看片| 久久国产精品99精品国产| 香蕉国产精品偷在线观看不卡|