算法一：
思想分析：
要求解序列中最大的和，那么需要得到，每个序列的和，并比较值
int[] a = {-1, 0, 1, 2, -3, 8, 6};
[-1]
[-1,0]
[-1,0,1]
…
[0]
[0,1]
[0,1,2]
…
这种算法，时间复杂度O(N^3)
/**
* 求最大子序列和 解法一：
*/
public static void main(String[] args) {
int[] a = {-1, 0, 1, 2, -3, 8, 6};
int b = maxSum1(a);
System.out.println(b);
}
public static int maxSum1(int[] a) {
int maxSum = 0;
for (int i = 0; i < a.length ; i++) { //循环大小为N
for (int j = i; j < a.length; j++) { //循环大小为 N-i
int thisSum = 0;
for (int k = i; k <= j ; k++) //循环大小为j -i + 1 (求和与比较放在一个循环也是ok的，这里分开了，只求和)
thisSum += a[k];
if (thisSum > maxSum) {
maxSum = thisSum;
}
}
}
return maxSum;
}
算法二：
这个只是对算法一进行了一些优化：
这种算法，时间复杂度O(N^2)
这里i 表示的序列的开始位置，不断推进开始位置，依次计算每个序列和，并把每轮求解的与最大值比较，把大于最大值的
当前值赋值给最大值。
public static int maxSum2(int[] a) {
int maxSum = 0;
for (int i = 0; i < a.length ; i++) {
int thisSum = 0;
for (int j = i; j < a.length; j++) {
thisSum += a[j];
if (thisSum > maxSum) {
maxSum = thisSum;
}
}
}
return maxSum;
}
算法四：
时间复杂度：O（N）
思想分析：
要求解序列中最大的和，那么需要得到，每个序列的和，并比较值
int[] a = {-1, 0, 1, 2, -3, 8, 6};
因为 -1, 0, 1, 2, -3 的 和 <0 因此序列的开始位置可以从
8 开始
这个算法中，对算法三进行了优化，如果一个序列的和出现负值，那么可以把起始点推进到 j+1 的位置
/**
* 经典算法：这个算法只对数据进行一次扫描，一旦a[i] 被读入并处理，就不需要被记忆，
* 因此，如果数组在磁盘上或通过互联网传送，那么它就可以按顺序读入，在主存中不必存
* 储数组的任何部分。
* 并且在任意时刻，算法都能对它已经读入的数据给出子序列问题的正确答案。（这种算法叫作联机算法）
*
* @param a
* @return
*/
public static int maxSubSum4(int[] a) {
int maxSum = 0,thisSum = 0;
for (int j = 0; j < a.length; j++) {
thisSum += a[j];
if (thisSum > maxSum) {
maxSum = thisSum;
} else if (thisSum < 0) {
thisSum = 0;
}
}
return maxSum;
}
今天的文章最大子序列和的四种算法_如何计算时间复杂度分享到此就结束了，感谢您的阅读。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/61652.html
