实例1.1 最大子列和问题

实例1.1 最大子列和问题 (20分)

思路分析：本题有三种基本的算法，分别为1.两个循环控制 2.二分法 3.在线处理，其中在线处理的时间复杂度为O(n),这是效率比较高得算法，所以选择它，在线处理的核心思想是，当前n项和小于0时，便舍弃当前计算的前n项和，并且将临时保存的最大值舍弃，然后再依次向下累加，题目中还说如果输入的数都为负数，那么便直接输出0，如果要检查都是负数的意思就是，只有要一个数是正整数数我们可以确保这个数组不全是负数

#include <iostream>
#define MAX 100000
using namespace std;

int main ()
{
    int num,flag =1,i=0;
    cin >> num;
    int array[MAX];
    while(i<num)
    {
        cin>>array[i];
        i++;
    }
    for(i = 0;i<num;i++)
    {
        if(array[i]>=0)
        {
            flag = 0;
            break;
        }
    }
    int maxSum = 0;
    int tempSum = 0;
    for(i = 0; i<num ; i++)
    {
        tempSum +=array[i];
        if(tempSum < 0)
        {
            tempSum = 0;
        }else if(tempSum>maxSum)
        {
            maxSum = tempSum;
        }
    }
    if(flag == 1)cout<<"0";
    else cout<<maxSum;
    return 0;
}

本文地址：https://blog.csdn.net/m0_43429389/article/details/107431331