欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

实例1.1 最大子列和问题

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

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

实例1.1 最大子列和问题思路分析:本题有三种基本的算法,分别为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