输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为1。求所有子数组的和的最大值。
数据范围:
要求:时间复杂度为 )
，空间复杂度为
进阶:时间复杂度为 ，空间复杂度为 )
[编程题]连续子数组的最大和
public int FindGreatestSumOfSubArray (int[] array) {
// write code here
int max=array[0];
for(int i=1;i<array.length;i++){
array[i]=Math.max(array[i] ,array[i]+array[i-1]);
max=Math.max(array[i] ,max);
}
return max;
}
发表于 2023-11-12 16:31:05
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param array int整型一维数组
* @return int整型
*/
public int FindGreatestSumOfSubArray (int[] array) {
// write code here
// 方法一：空间复杂度O(n)
// dp[i]表示以num[i]结尾的数组最大和
// int[] dp = new int[array.length];
// dp[0] = array[0];
// int max = array[0];
// for (int i = 1; i < array.length; i++) {
// if (dp[i - 1] > 0) {
// dp[i] = dp[i - 1] + array[i];
// } else dp[i] = array[i];
// max = dp[i] > max ? dp[i] : max;
// }
// return max;
// 方法二：空间复杂度O(1)
// 记录子数组和
int sum = array[0];
// 记录最大子数组和
int res = array[0];
for (int i = 1; i < array.length; i++) {
// 原子数组和为正，则原子数组与当前元素组成的子数组和大于以当前元素
// 单独构成的子数组
if (sum > 0) sum = sum + array[i];
// 原子数组和不为正，则原子数组与当前元素组成的子数组和小于以当前元素
// 单独构成的子数组，则以当前元素作为新的最大子数组
else sum = array[i];
// 记录最大值
res = sum > res ? sum : res;
}
return res;
}
}
发表于 2023-10-30 12:57:49
回复(0)
public int FindGreatestSumOfSubArray(int[] array) {
if(array.length==1){
return array[0];
}
int[] dp=new int[array.length];
dp[0]=array[0];
int ans=array[0];
for(int i=1;i<array.length;i++){
dp[i]=Math.max(dp[i-1]+array[i],array[i]);
ans=Math.max(ans,dp[i]);
}
return ans;
}
发表于 2023-05-31 22:05:41
回复(0)
//时间超了。。。。
public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
int max = Integer.MIN_VALUE;
for (int i = 0; i < array.length; i++) {
for (int j = i; j < array.length; j++) {
int tempsum = 0;
for (int k = i; k <= j; k++) {
tempsum += array[k];
}
max = Math.max(tempsum, max);
}
}
return max;
}
}
发表于 2023-03-26 10:34:33
回复(0)
// 递归 + dp优化 = 动态规划
public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
int[] dp = new int[array.length];
for (int i = 0; i < dp.length; i++) {
dp[i] = -1;
}
int max = Integer.MIN_VALUE;
for (int i = 0; i < array.length; i++) {
int maxSum = getMaxSum(array, i, dp);
dp[i] = maxSum;
if (maxSum > max) max = maxSum;
}
return max;
}
private int getMaxSum(int[] array, int cur, int[] dp) {
if (cur == 0) {
return array[0];
}
return Math.max(dp[cur - 1] + array[cur], array[cur]);
}
}
发表于 2023-03-10 11:56:25
回复(0)
public class Solution {
/**
* 时间复杂度O(n) 空间复杂度O(n)
* 假设数组: 1,-2,3,10,-4,7,2,-5
* 每次找到以 i 结尾的最大子数组之和
* n[0] = 1
* n[1] = Max(-2, (-2 + n[0]->1)) = -1
* n[2] = Max(3, (3 + n[1]->-1 )) = 3
* n[3] = Max(10, (10 + n[2]->3 )) = 13
* n[4] = Max(-4, (-4 + n[3]->13 )) = 9
* n[5] = Max(7, (7 + n[4]->9 )) = 16
* n[6] = Max(2, (2 + n[5]->16 )) = 18
* n[7] = Max(-5, (-5 + n[6]->18 )) = 13
* 由此得知，最大子数组之和为18
* *****************************************************
* 时间复杂度O(n) 空间复杂度O(1)
* 数组从下标1开始遍历，因为以下标0结尾的最大子数字之和，只有它自己，所以为固定值
* 每次遍历，都是求最大值 Max(当前元素+前驱元素的子数组之和 , 当前元素) ，即为当前元素的子数组最大和
* 所以可以取消dp数组， 采用一个max记录最大子数组之和，一个pre记录前驱元素的子数组之和即可
* 解法如下：
*/
public int FindGreatestSumOfSubArray(int[] array) {
// 记录数组最大值，初始值为第一个元素
int max = array[0];
// pre用于记录循环中 i索引位置的前一位数字的最大子数组之和
// 初始值为第一个元素
int pre = array[0];
// 从第二个元素开始遍历，每次循环，求最大值 Max(当前元素+前置元素的子数组之和 , 当前元素) ，即为当前元素的子数组最大和
// 即每次循环都在找以i结尾的数组元素，子数组最大之和
for (int i = 1; i < array.length; i++) {
// 将计算出来的当前元素子数组最大和，赋予pre，下次循环时即为 i的前置元素最大和
pre = Math.max(array[i] + pre, array[i]);
// 当前元素计算出以i结尾的子数组最大之和后，与max相比取最大值，再重新赋予max
max = Math.max(max, pre);
}
// 循环结束max即为解
return max;
}
}
发表于 2022-11-26 22:38:32
回复(0)
public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
if (array.length == 0 || array == null) {
return 0;
}
int temp = 0;
int max = array[0];
for (int i = 0; i < array.length; i++) {
if (temp <= 0) {
temp = array[i];
if (temp > max) {
max = temp;
}
} else {
temp += array[i];
if (temp > max) {
max = temp;
}
}
}
return max;
}
}
发表于 2022-10-23 11:11:30
回复(0)
public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
//默认第一个为最大
int max = array[0];
//array[i]以array结尾的最大子数组和
for (int i = 1; i < array.length; i++) {
//前一个子数组的和是否对于当前子数组有增量？
//有的话加上前一个子数字的和
//没有的话加0
array[i]+= Math.max(array[i - 1], 0);
//同时找最大值
max = Math.max(max, array[i]);
}
return max;
}
}
发表于 2022-09-17 09:28:13
回复(0)
public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
int max = array[0];
int[] dp = new int[array.length];
dp[0] = array[0];
for (int i = 1; i < array.length; i++) {
dp[i] = Math.max(array[i], dp[i - 1] + array[i]);
if (dp[i] > max) max = dp[i];
}
return max;
}
}
发表于 2022-09-16 09:37:26
回复(0)
问题信息
难度：
272条回答
3007收藏
155561浏览
通过挑战的用户
-
2023-03-08 10:26:42
-
2023-03-03 20:52:51
-
2023-02-26 11:32:37 -
2023-02-24 16:57:17 -
2023-02-18 18:10:42
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
public class Solution { public int FindGreatestSumOfSubArray(int[] array) { if (array.length==0 || array==null) { return 0; } int curSum=0; int greatestSum=0x80000000; for (int i = 0; i < array.length; i++) { if (curSum<=0) { curSum=array[i]; //记录当前最大值 }else { curSum+=array[i]; //当array[i]为正数时，加上之前的最大值并更新最大值。 } if (curSum>greatestSum) { greatestSum=curSum; } } return greatestSum; } }