输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为1。求所有子数组的和的最大值。
数据范围:
要求:时间复杂度为 )
，空间复杂度为
进阶:时间复杂度为 ，空间复杂度为 )
[编程题]连续子数组的最大和
#define MIN_VAL -101
int FindGreatestSumOfSubArray(int* array, int arrayLen )
{
// write code here
if(array == NULL || arrayLen == 0)
return 0;
int sum = MIN_VAL,ret = MIN_VAL;
for(int i=0;i<arrayLen;i++)
{
if(sum+array[i] > array[i])
sum +=array[i];
else
sum = array[i];
if(ret < sum)
ret = sum;
}
return ret;
}
发表于 2023-05-25 14:17:38
回复(0)
int FindGreatestSumOfSubArray(int* array, int arrayLen ) {
// write code here
int max = -101 , num = 0;
for(int i = 0 ; i < arrayLen ; i++){
num += array[i];
if(num > max){
max = num;
}
if(num < 0){
num = 0;
}
}
return max;
}
发表于 2023-03-28 11:16:41
回复(0)
int MaxSonArray(int array[],int end){
int dp,i,max;
dp = max = array[0];
for(i=1;i<end;i++){
dp = array[i] + ((dp < 0)?0:dp);
if(dp > max) max = dp;
}
return max;
}
int dp,i,max;
dp = max = array[0];
for(i=1;i<end;i++){
dp = array[i] + ((dp < 0)?0:dp);
if(dp > max) max = dp;
}
return max;
}
int FindGreatestSumOfSubArray(int* array, int arrayLen ) {
// write code here
return MaxSonArray(array,arrayLen);
}
发表于 2022-12-15 20:15:45
回复(0)
int FindGreatestSumOfSubArray(int* array, int arrayLen )
{
int i,j;
int sum=0;
int sum1=array[0];
for(i=0;i<arrayLen;i++)
{
if(sum<0)
{
sum=array[i];
}
else
{
sum=sum+array[i];
}
if(sum>sum1)
sum1=sum;
}
return sum1;
}
发表于 2022-10-12 23:07:25
回复(0)
/**
*
* @param array int整型一维数组
* @param arrayLen int array数组长度
* @return int整型
*
* C语言声明定义全局变量请加上static，防止重复定义
*
* C语言声明定义全局变量请加上static，防止重复定义
*/
int FindGreatestSumOfSubArray(int* array, int arrayLen ) {
// write code here
int maxvalue=array[0];
int* s=(int*)malloc(sizeof(int)*arrayLen);
s[0]=array[0];
for(int i=1;i<arrayLen;i++){
if((s[i-1]+array[i])>=array[i])
s[i]=s[i-1]+array[i];
else
s[i]=array[i];
if(maxvalue<s[i])
maxvalue=s[i];
}
return maxvalue;
}
发表于 2022-05-05 11:59:00
回复(0)
#define MAX(a,b) ((a)>(b)?(a):(b))
int FindGreatestSumOfSubArray(int* array, int arrayLen ) {
// write code here
int dp[200001] = {0};
int i ,max;
dp[0] = array[0];
max = array[0];
for(i=1;i<arrayLen;i++){
dp[i] = MAX(dp[i-1]+array[i],array[i]);
max = MAX(max,dp[i]);
}
return max;
}
int FindGreatestSumOfSubArray(int* array, int arrayLen ) {
// write code here
int dp[200001] = {0};
int i ,max;
dp[0] = array[0];
max = array[0];
for(i=1;i<arrayLen;i++){
dp[i] = MAX(dp[i-1]+array[i],array[i]);
max = MAX(max,dp[i]);
}
return max;
}
发表于 2022-04-17 18:44:36
回复(1)
/**
*
* @param array int整型一维数组
* @param arrayLen int array数组长度
* @return int整型
*
* C语言声明定义全局变量请加上static，防止重复定义
*/
int FindGreatestSumOfSubArray(int* array, int arrayLen ) {
// write code here
int sum,max;
max = -100,sum = 0;
for(int i=0; i<arrayLen; i++)
{
sum += array[i];
if(sum > max ) max = sum;
if(sum < 0 ) sum = 0; //舍弃前面<0的和
}
return max;
}
发表于 2021-12-25 21:50:24
回复(0)
问题信息
难度：
15条回答
3007收藏
155564浏览
通过挑战的用户
-
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; } }