实例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.两个循环控制 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