PAT1007

暴力解法

https://pintia.cn/problem-sets/994805342720868352/problems/994805514284679168

#include<cstdio>

int num[10005];

int main()
{
    int k;

    scanf("%d",&k);
    for(int i = 0;i < k;i++)
    {
        scanf("%d",&num[i]);
    }
    int sum=0,first=0,last=k-1;

    for(int i = 0;i < k;i++)
    {
        int tSum=0;
        for(int j = i;j < k;j++)
        {
            tSum += num[j];
            if(tSum > sum ||(tSum == sum &&tSum == 0))
            {
                first = i;
                last = j;
                sum = tSum;
            }
        }
    }

    printf("%d %d %d\n",sum,num[first],num[last]);


    return 0;
}

非暴力写法， 来源

#include <iostream>
#define mm 10001
using namespace std;
int maxsequence3(int a[], int len);
int start=0;
int last=0; 
int main()
{
	int M,arr[mm]={0};
	int max=0;
	cin>>M;
	for(int i=0;i<M;i++)
		cin>>arr[i];
	int j=0;
	while(arr[j]<0&&j<M)
		j++;
	if(j==M)
	{
		cout<<"0 "<<arr[0]<<" "<<arr[M-1];
		return 0;
	}
	int sum=maxsequence3(arr, M);
	cout<<sum<<' '<<arr[start]<<' '<<arr[last];
	return 0;
}
int maxsequence3(int a[], int len)
{
    int maxsum, maxhere,temp_start,temp_last;
    temp_start=0;
	temp_last=0;
	maxsum=a[0]; 
	maxhere=a[0];   //初始化最大和为a【0】
    for (int i=1;i<len;i++) 
	{
        if (maxhere<= 0)
        {
        	 maxhere=a[i];  //如果前面位置最大连续子序列和小于等于0，则以当前位置i结尾的最大连续子序列和为a[i]
        	 temp_start=i;
		}
           
        else
        {
        	maxhere+=a[i]; //如果前面位置最大连续子序列和大于0，则以当前位置i结尾的最大连续子序列和为它们两者之和
        	temp_last=i;
		}
            
        if (maxhere>maxsum)
		 {
            maxsum=maxhere;  //更新最大连续子序列和
            start=temp_start;
            last=temp_last;
        }
    }
    if(start>last)
    last=start;//避免出现下面状况start不断更新，而last保持第一个不变，所以额外添加这个if判断语句，如果输入序列为 -1 -2 -3 0 -4，这个if判断就是必须的 
    return maxsum;
}