首页 > 代码库 > 一个有N个整数元素的一维数组{A[0],A[1],....,A[N-1],A[N]},这个数组有很多连续的子数组，那么连续子数组之和的最大的一个的值是什么？
一个有N个整数元素的一维数组{A[0],A[1],....,A[N-1],A[N]},这个数组有很多连续的子数组，那么连续子数组之和的最大的一个的值是什么？
1.动态规划的思想解决
/**
* 在时间复杂度为O(N)内找出数组中最大的子序列的累加和
*/
public static int sumNum(int[] array) {
int n = array.length;
int all = array[n - 1], start = array[n - 1];
int count = 0;
for (int i = n - 2; i >= 0; i--) {
if ((start + array[i]) > array[i]) {
start = start + array[i];
} else {
start = array[i];
}
if (all < start) {
all = start;
}
count++;
}
System.out.println("数组长度:" + array.length + ", 时间复杂度:" + count);
System.out.println("最大值" + all);
return all;
}
一个有N个整数元素的一维数组{A[0],A[1],....,A[N-1],A[N]},这个数组有很多连续的子数组，那么连续子数组之和的最大的一个的值是什么？
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。