午夜在线一区,国产日韩在线视频,激情成人综合网

最大的子序列和問題

求解該問題的四種算法：
時間O(N³)，算法一

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(N²)，算法二

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 閱讀(1081) 評論(7) 編輯收藏引用所屬分類: 算法、筆記

輸入如下：-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;
} 回復更多評論

刷新評論列表

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: 列出所有9位數，它的前n位能被n整除最大的子序列和問題全排列算法求解(還沒有人做出來，唉) string和int間的類型轉換

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

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

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

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

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

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

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

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

Dain

導航

公告

隨筆分類(16)

文章分類(7)

隨筆檔案(15)

文章檔案(5)

統計

留言簿(3)

積分與排名

良師益友

閱讀排行榜

評論排行榜

最大的子序列和問題

評論