`

【100题】第三题(数组(元素可为正数、负数、0)的最大子序列和)

 
阅读更多

3,输入一个整型数组,数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。

例如:输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2,
因此输出为该子数组的和18。

解题思路:当我们加上一个正数时,和会增加;当我们加上一个负数时,和会减少。如果当前得到的和是个负数,那么这个和在接下来的累加中应该抛弃并重新清零,不然的话这个负数将会减少接下来的和。

程序源码:

#include <iostream.h>
int get_sub_sum_max(int *arr, int len)
{
int max, sum;

max = arr[0]; //存储最大子数组 和
sum = 0; //判断 一直相加后 是否为负数 从而影响后面再相加
while (len--)
{
sum += *arr++; //下一个数组 元素 遇到负数 则清零

if (sum >=max)//当加上一个负数时 max 没有改变 观察后面加许多值后有木有 大于 max的
max = sum; //max存储sum 不是零的数后 ,再与下一轮 sum+arr[i] 后相比
else if (sum < 0) //当前的和为负数,则影响下一个数
sum = 0;
}
return max;
}
int main()
{
// int a[10]={1,-8,6,3,-1,5,7,-2,0,1}; //这个数组 必须结果是 20
int a[8]={1, -2, 3, 10, -4, 7, 2, -5}; //这个数组 必须 结果是 18
// int a[10]={-1,-2,-3,-4,-5,-6,-7,-8,-9,-10};
printf("%d\n",get_sub_sum_max(a,8));

return 0;
}

int a[8]={ 1, -2, 3, 10, -4, 7, 2, -5};

max=1;sum=1

max=1;sum=-1 -->sum=0

max=3;sum=3

max=13;sum=13

max=13;sum=9

max=16;sum=16

max=18;sum=18

max=18;sum=13

返回 max=18

这里给出了详细解答:http://blog.csdn.net/v_JULY_v/article/details/6444021

分享到:
评论

相关推荐

    PHP求最大子序列和的算法实现

    2. 初始化两个下标变量`$start`和`$end`,用于记录最大子序列的起始和结束位置,初始值分别为0。 3. 遍历数组中的每个元素,将元素值累加到`$thissum`上。 4. 如果`$thissum`大于`$maxsum`,则更新`$maxsum`并记录...

    连续子序列最大和与乘积问题的分析

    连续子序列最大和问题(也称为“最大子数组和问题”)的目标是找到一个数组中的连续子数组,使得其和最大。最著名的解法是 Kadane's Algorithm。该算法以O(n)的时间复杂度完成,遍历一次数组,同时记录当前子数组的...

    求最大子数组之和的方法解析(2种可选)

    这个问题的目标是在一个包含正数和负数的数组中找到连续子数组,使得子数组的和最大。 **方法1:蛮力法** 这种方法通过双重循环来遍历所有可能的子数组,并计算它们的和,然后在这些和中找到最大的。虽然直观易懂,...

    课件5_5 P411

    2. **动态规划策略**:我们可以使用一个名为“b[j]”的辅助数组来存储从数组开始到当前位置j的最大子序列和。初始时,b[j]等于数组的第一个元素。对于后续的每个元素,根据以下规则更新b[j]: - 如果前一个子序列和b...

    MAX SUM {a1,a2,…,an},求该序列形如ai+ai+1,…,+aj的子段和的最大值

    本题目要求解决的问题是“最大子数组和问题”,即给定一个整数序列{a1, a2, …, an}(这些整数可以为正数也可以为负数),我们需要找到一个连续的子序列,使得这个子序列的所有元素之和最大,并返回这个最大和。...

    程序设计培训讲义5:排序与查找.pptx

    如果数组全为负数,最大子序列和为0。对于正数和负数交替的情况,二分查找可以有效地找到最大子序列和,但通常动态规划(如Kadane's algorithm)是首选方法,因为它在O(n)时间内完成,且空间复杂度较低。 ```c // ...

    常考的数据结构题_面试常用

    最大子序列问题 给定一个包含正数和负数的整数序列,找到其中子序列的最大和。 **解决方法**:可以使用动态规划的方法来解决此问题。核心思路是维护一个当前最大值和全局最大值,遍历整个序列,计算每个位置上...

    数据结构面试

    #### 三、最大子序列和 **3.1 最大子序列和问题** 给定一个整数序列,可能存在正数和负数,找出一个子序列,使得该子序列的和最大。 **算法思路**: - **穷举法**:遍历所有可能的子序列并计算它们的和,选择最大...

Global site tag (gtag.js) - Google Analytics