公告:欢迎访问,查看更多资源请点我^.^!            点我关闭广告
最大子序列和的四种算法
2018-08-27 11:56:00
1255人阅读
评论(0)
分类:算法

一 穷举法
public int getMax(int[] a) {
int maxSum = 0, sum;
for (int i = 0; i < a.length; i++) {
for (int j = i; j < a.length; j++) {
sum = 0;
for (int k = i; k < j; k++) {
sum += a[k];
}
if (sum > maxSum) {
maxSum = sum;
}
}
}
return maxSum;
}
时间复杂度为:O(N^3)

二 穷举法改进
public int getMax(int[] a) {
int maxSum = 0, sum;
for (int i = 0; i < a.length; i++) {
sum = 0;
for (int j = i; j < a.length; j++) {
sum += a[j];
if (sum > maxSum) {
maxSum = sum;
}
}
}
return maxSum;
}
时间复杂度为:O(N^2)

三 分而治之法
public int getMax(int[] a, int left, int right) {
if (left == right) {
return a[left] > 0 ? a[left] : 0;
}
int center = (left + right) / 2;
int maxLeftSum = getMax(a, left, center);
int maxRightSum = getMax(a, center + 1, right);

int maxLeftBorderSum = 0, leftSum = 0;
for (int i = center; i >= left; i--) {
leftSum += a[i];
if (leftSum > maxLeftBorderSum) {
maxLeftBorderSum = leftSum;
}
}

int maxRightBorderSum = 0, rightSum = 0;
for (int i = center + 1; i <= right; i++) {
rightSum += a[i];
if (rightSum > maxRightBorderSum) {
maxRightBorderSum = rightSum;
}
}

return max(maxLeftSum, maxRightSum, maxLeftBorderSum + maxRightBorderSum);
}
private int max(int x, int y, int z) {
return x > y ? (x > z ? x : z) : (y > z ? y : z);
}
时间复杂度为:O(Nlog(N))



四 最优起点法
public int getMax(int[] a) {
int maxSum = 0, sum = 0;
for (int i = 0; i < a.length; i++) {
sum += a[i];
if (sum > maxSum) {
maxSum = sum;
} else if (sum < 0) {
sum = 0;
}
}
return maxSum;
}
时间复杂度为:O(N)

分享一下:
赞一下(2)
博主资料
博主头像
zc521106
文章:34
浏览:19899
文章分类
Java(12)
NoSql(112)
数据库(12)
前端(12)
阅读排行
Java基础知识
(12)
NoSql应用
(112)
数据库Oracle语法
(12)
前端常用工具类
(12)
java web项目
(12)
linux安装mysql
(12)
评论区
这篇文章怎么样?写点评论吧!
姓名:
邮箱:
有回复时通知我:
发表
回复【10.20.30.32】:
暂无评论,快抢沙发!
* 以上用户言论只代表其个人观点,不代表iBlog网站的观点或立场,如有任何疑问请随时联系管理员...