首页 > 试题广场 >

最大连续子序列

[编程题]最大连续子序列
  • 热度指数:10897 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
    给定K个整数的序列{ N1, N2, ..., NK },其任意连续子序列可表示为{ Ni, Ni+1, ..., Nj },其中 1 <= i <= j <= K。最大连续子序列是所有连续子序列中元素和最大的一个,例如给定序列{ -2, 11, -4, 13, -5, -2 },其最大连续子序列为{ 11, -4, 13 },最大和为20。现在增加一个要求,即还需要输出该子序列的第一个和最后一个元素。

输入描述:
    测试输入包含若干测试用例,每个测试用例占2行,第1行给出正整数K( K< 10000 ),第2行给出K个整数,中间用空格分隔。当K为0时,输入结束,该用例不被处理。


输出描述:
    对每个测试用例,在1行里输出最大和、最大连续子序列的第一个和最后一个元素,中间用空格分隔。如果最大连续子序列不唯一,则输出序号i和j最小的那个(如输入样例的第2、3组)。若所有K个元素都是负数,则定义其最大和为0,输出整个序列的首尾元素。
示例1

输入

6
-2 11 -4 13 -5 -2
10
-10 1 2 3 4 -5 -23 3 7 -21
6
5 -8 3 2 5 0
1
10
3
-1 -5 -2
3
-1 0 -2
0

输出

20 11 13
10 1 4
10 3 5
10 10 10
0 -1 -2
0 0 0
//悟空大佬的思路, 我加了注释, 感觉sum这个思路真的太厉害了
#include<stdio.h>
#define max(a,b) a>b?a:b
int a[10005],Sum[10005];
int main()
{
    int n,i, Max,sum,flag,f,l,last;
    while(scanf("%d",&n)!=EOF&&n)
    {
        sum=0,Max=-999999999,flag=1;
        for(i=1;i<=n;i++)//逐个输入直接比较
        {
            scanf("%d",&a[i]);
            if(a[i]>=0) flag=0;//flag表示是否全部为负数
            sum=max(sum+a[i],a[i]);//比较sum到底是加上新的数还是新的数自己
            if(Max<sum)
            {
                Max=sum;
                last=i;//记录尾巴
            }
            Sum[i]=a[i]+Sum[i-1];//Sum数组是从头到尾的序列和
        }
        if(flag==1) printf("0 %d %d\n",a[1],a[n]);//全是负数的时候输出0, 从头到尾
        else{
            for(i=0;i<=n;i++)
                if(Sum[last]-Sum[i]==Max)//找出到底是哪段序列最大记录开始下标i
                    break;
            printf("%d %d %d\n",Max,a[i+1],a[last]);
        }
    }
}

编辑于 2020-04-14 21:07:16 回复(0)
为何这里冷冷清清的
发表于 2017-09-05 02:02:46 回复(0)
//写一点功能就先测试一下
#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;//又忘记写了,导致sort函数报错

const int MAXN = 10001;
int a[MAXN];
struct DP
{
    int num;
    int left;
    int right;
};
DP dp[MAXN];

bool Compare(DP a,DP b)//写的位置也有要求
{
    return a.num > b.num;
}

int judge(int n)
{
    for(int i=0; i<n; ++i)
    {
        if(a[i] > 0)
        {
            return 0;
        }
    }
    return 1;
}

int main()
{
    int n;
    while(scanf("%d",&n) != EOF)
    {
        if(n == 0)
        {
            break;
        }
        for(int i=0; i<n; ++i)
        {
            scanf("%d",&a[i]);
        }
        if(judge(n))
        {
            printf("0 %d %d\n",a[0],a[n-1]);//平时for里面默认n-1习惯了,这里忘写了
        }
        dp[0].num = a[0];
        dp[0].left = a[0];
        dp[0].right = a[0];
        for(int i=1; i<n; ++i)
        {
            if(dp[i-1].num+a[i] > a[i])//忘记加.num了
            {
                dp[i].num = dp[i-1].num+a[i];
                dp[i].left = dp[i-1].left;
                dp[i].right = a[i];
            }
            if(a[i] > dp[i-1].num+a[i])
            {
                dp[i].num = a[i];
                dp[i].left = a[i];
                dp[i].right = a[i];
            }
        }
        sort(dp,dp+n,Compare);//Compare不用加括号,又被自动补全骗了
        printf("%d %d %d",dp[0].num,dp[0].left,dp[0].right);
    }
    return 0;
}



发表于 2021-05-11 09:53:36 回复(0)
#include<iostream>
using namespace std;

int dp[10000];

int main()
{
    int K,d;
    while(cin >> K && K)
    {
        int t1,t2,t3,maxsum,start,end;
        cin >> d;
        dp[0] = d;
        maxsum = dp[0];
        t1 = dp[0];
        t2 = t1;
        t3 = t1;
        start = end = t1;
        for(int i = 1;i < K;i++)
        {
            cin >> d;
            if(i == K - 1) end = d;
            if(d > d + dp[i - 1])
            {
                t1 = d;
                dp[i] = d;
            }
            else
            {
                dp[i] = d + dp[i - 1];
            }
            if(maxsum < dp[i])
            {
                maxsum = dp[i];
                t2 = t1;
                t3 = d;
            }
        }
        if(maxsum < 0)
            cout << 0 << " " << start << " " << end << endl;
        else
            cout << maxsum << " " << t2 << " " << t3 << endl;
    }
    return 0;
}

发表于 2021-02-08 10:34:10 回复(0)
动态规划求最大连续序列和
最后找首尾比较麻烦罢了
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    while(cin>>n&&n!=0)
    {
        int a[10001]={0},dp[10001]={0};
        for(int i=0;i<n;++i)
            cin>>a[i];
        dp[0]=a[0];
        for(int i=1;i<n;++i)
        {
            if(dp[i-1]<0)dp[i]=a[i];
            else dp[i]=dp[i-1]+a[i];
        }
        int max=0;
        for(int i=1;i<n;++i)
            if(dp[i]>dp[max])max=i;
        if(dp[max]<0)cout<<0<<" "<<a[0]<<" "<<a[n-1]<<endl;
        else
        {
            int count=0,min;
            for(int i=max;i>=0;--i)
            {
                count+=a[i];
                if(count==dp[max])min=i;
            }
            cout<<dp[max]<<" "<<a[min]<<" "<<a[max]<<endl;
        }
    }
}


发表于 2021-01-28 23:00:43 回复(0)
#include<iostream>
using namespace std;

int num[10000]={0};
int main(){
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",&num[i]);
	}
	long long temp,answer;//局部变量并不会自动初始化,全局变量才会自动初始化 
	int begin,last;
	temp=0;
	answer=0;
	int tag=0; 
	for(int i=0;i<n;i++){
		temp+=num[i];
		if(temp<0){
			temp=0;
		}
		if(temp>answer){
			answer=temp;
			last=num[i];
			tag=i;
		}	
	}
	int cache=answer;
	for(;cache!=0;tag--){
		cache-=num[tag];
	}
	
	printf("%d %d %d",answer,num[tag+1],last);	
	
} 

发表于 2021-01-22 18:49:32 回复(0)
import java.util.Scanner;

/**
 * @author Wangjs
 * @version 1.0
 * @date 2021/1/13 15:22
 */
public class Main {
    private static int[] solve(int[] nums) {
        int[] ret = new int[3];
        int n = nums.length;
        int ans = nums[0];
        int dp = nums[0];
        int r = 0;
        int len = 1;
        int realLen = 1;
        for(int i = 1; i < n; i++) {
            if(dp > 0) {
                dp = dp + nums[i];
                len++;
            } else {
                dp = nums[i];
                len = 1;
            }
            // 更新全局最大值的同时, 更新长度
            if(dp > ans) {
                ans = dp;
                r = i;
                realLen = len;
            }
        }
        if(ans >= 0) {
            ret[0] = ans; ret[1] = nums[r - realLen + 1]; ret[2] = nums[r];
        } else {
            ret[0] = 0; ret[1] = nums[0]; ret[2] = nums[n - 1];
        }
        return ret;
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        while(scan.hasNext()) {
            int n = scan.nextInt();
            if(n == 0) {
                break;
            }
            int[] nums = new int[n];
            for(int i = 0; i < n; i++) {
                nums[i] = scan.nextInt();
            }
            // ans: 全局最大值
            int[] ret = solve(nums);
            System.out.printf("%d %d %d\n", ret[0], ret[1], ret[2]);
        }
    }
}

发表于 2021-01-13 15:37:28 回复(0)
#include<iostream>
#include<algorithm>
using namespace std;
struct note
{
	int sum, first, last;
	note() {}
	//note(int a, int b, int c) :sum(a), first(b), last(c) {}
	note(int a) :sum(a), first(a), last(a) {}
};
note max_subsequence(int*& arr, int& n)
{
	note dp(arr[0]);//dp表示以i 为结尾时最长子序列和
	note max = dp;
	for (int i = 1; i < n; i++)
	{
		if (arr[i] > dp.sum + arr[i])
		{
			dp.sum = arr[i];
			dp.first = dp.last = arr[i];
		}
		else
		{
			dp.sum = dp.sum + arr[i];
			dp.last = arr[i];
		}
		if (max.sum < dp.sum)
			max = dp;
	}
	if (max.sum < 0)
	{
		max.sum = 0;
		max.first = arr[0];
		max.last = arr[n - 1];
	}
	return max;
}

int main()
{
	int n;
	note ans;
	while (cin>>n && n != 0)
	{
		int* arr = new int[n];
		for (int i = 0; i < n; i++)
			cin >> arr[i];
		ans = max_subsequence(arr, n);
		cout << ans.sum << " " << ans.first << " " << ans.last<< endl;
		delete[] arr;
	}
	return 0;
}

发表于 2020-07-09 14:54:28 回复(0)
#include<iostream>
(720)#include<algorithm>
using namespace std;
const int maxn=10005;
int a[maxn];
int dp[maxn];
void MaxSubSequence(int n)
{
    int maximum=-0xffff;
    int sum=0;//检测其中有多少负数
    int begin=0;
    int end=0;
    for(int i=0;i<n;i++)
    {
        if(a[i]<0)
            sum++;
        if(i==0)
            dp[i]=a[i];
        else{
            dp[i]=max(dp[i-1]+a[i],a[i]);
        }
        if(dp[i]>maximum)//更新下标
             end=i;
        maximum=max(maximum,dp[i]);
    }
    if(sum==n)//表示全为负数
        cout<<"0"<<" "<<a[0]<<" "<<a[n-1]<<endl;
    else{
        int i=end;
        while(dp[i]>=0&&i>=0)
            i--;//找到最大子序列和下标前使dp[i]<0的下标再加一即为begin下标;
        begin=i+1;
        cout<<dp[end]<<" "<<a[begin]<<" "<<a[end]<<endl;
    }
}
int main()
{
    int K;
    while(cin>>K)
    {
        if(K==0)
            break;
        for(int i=0;i<K;i++)
            cin>>a[i];
        MaxSubSequence(K);
    }
    return 0;
}

发表于 2020-04-07 18:28:07 回复(0)
我贴一个用书上的二分法代码吧,时间复杂度是O(nlogn):
思想是分成两半,同时考虑跨越分割点的子列。
//使用二分法求最大和的连续子列
//注意操作符的重载和求最大值时初始值的处理
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;


#define UNKNOWN -1
struct Record {
    int sum;
    int l, h;
    Record() {}
    Record(int vsum, int vl, int vh): sum(vsum), l(vl), h(vh) {}
    bool operator< (const Record& b) const {
        if(l == UNKNOWN) {
            return true;
        }else  if( sum == b.sum){
            if(l == b.l) return h > b.h;
            else return l > b.l;
        }else{
            return sum < b.sum;
        }
    }
    void operator=(const Record& b) {
        sum = b.sum;
        l = b.l;
        h = b.h;
    }
};

bool FindMaxArr(const vector<int>& arr, int l, int h,  Record& res) {
    if(l > h) {
        return false;
    } else if(l == h) {
        res = max(res, Record(arr[l], l, h));
        return true;
    } else {
        //在左侧子列中查找
        int mid = (l + h) / 2;
        Record r1(0, UNKNOWN, UNKNOWN);
        if(FindMaxArr(arr, l, mid, r1)) {
            res = max(res, r1);
        }
        //在右侧字表中查找
        Record r2(0, UNKNOWN, UNKNOWN);
        if(FindMaxArr(arr, mid + 1, h, r2)) {
            res = max(res, r2);
        }

        //对跨越中间点的情况进行查找
        int sum_mid_max;
        int sum_left = 0;
        int index1 = mid + 1;//以防左端没有元素的情况,可以考虑先判断是否有元素再进行计算
        int sum_left_max = 0;
        for(int i = mid; i >= l; --i) {
            sum_left += arr[i];
            if(index1 == mid + 1 || sum_left > sum_left_max) {
                index1 = i;
                sum_left_max = sum_left;
            }
        }
        int sum_right = 0;
        int index2 = mid;//以防右端没有元素的情况
        int sum_right_max = 0;
        for(int i = mid + 1; i <= h; ++i) {
            sum_right += arr[i];
            if(index2 == mid || sum_right > sum_right_max) {
                index2 = i;
                sum_right_max = sum_right;
            }
        }
        sum_mid_max = sum_left_max + sum_right_max;
        Record r3(sum_mid_max, index1, index2);
        res = max(res, r3);

        return true;
    }
}

int main() {
    int n;
    vector<int> arr;
    while(cin >> n && n > 0) {
        arr.clear();
        arr.resize(n);
        int negtive_num = 0;
        for(int i = 0; i < n; ++i) {
            cin >> arr[i];
            if(arr[i] < 0)
                ++negtive_num;
        }
        if(negtive_num == n) {
            cout << 0 << " " << arr[0] << " " << arr[n-1]<< endl;
        } else {
            Record res(0, UNKNOWN, UNKNOWN);
            if(FindMaxArr(arr, 0, n - 1, res)) {
                cout << res.sum << " " << arr[res.l] << " " << arr[res.h] << endl;
            } else {
                cout << 0 << " " << 0 << " " << 0 << endl;
            }
        }
    }
    return 0;
}



编辑于 2020-03-27 16:49:31 回复(0)
///方法一:只保存最后一个下标以及最大和   然后通过最大和和最后一个下标计算出第一个
#include <cstring>
#include <iostream>
using namespace std;
#define N 10000

int main(){
    int a[N];
    int k,i,num_negitave;
    while(cin >> k){
        if(k==0) break;
        num_negitave=0;
        for(i=0;i<k;i++){
            cin >> a[i];
            if(a[i]<0){
                ++num_negitave;
            }
        }
        if(num_negitave==k){///全是负数 
            cout << "0 " << a[0] << " " << a[k-1] << endl;
            continue;
        }
        int sum=a[0],max_sum=a[0];
        int last=0;
        for(i=1;i<k;i++){///找最大连续和 
            if(sum < 0) sum = 0;
            sum+=a[i];
            if(sum>max_sum){
                last = i;   ////保存最后一个下标 
                max_sum = sum;
            }
        }
        cout << max_sum <<" ";
        for(i=last;i>=0;--i){
            if(max_sum-a[i]==0){
                cout << max_sum << " "; ////计算第一个 
                break;
            }else{
                max_sum-=a[i];
            }
        }
         cout << a[last] << endl; 
    }
    return 0;
}

//////////////////////////////////////////////////////////////////DP////////////////////////////////////////////////////////////////////////////////////////

发表于 2019-03-19 20:59:48 回复(0)
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            int K = in.nextInt();
            if(K==0) break;
            int[] arr = new int[K];
            int flag = 1;
            for(int i=0;i<K;i++){
                arr[i] = in.nextInt();
                if(arr[i]>0) flag=0; 
            }
            if(flag==1){
                System.out.printf("%d %d %d\n",0,arr[0],arr[K-1]);
                continue;
            }
            int[] dp = new int[K];
            dp[0] = arr[0];
            for(int i=1;i<K;i++){
                if(dp[i-1]+arr[i]>arr[i])
                    dp[i] = dp[i-1]+arr[i];
                else
                    dp[i] = arr[i];
            }
            int max = dp[0];
            int idx = 0;
            for(int i=1;i<K;i++)
                if(dp[i]>max){
                    max = dp[i];
                    idx = i;
                }
            int begin=idx;
            for(int sum=arr[idx]; sum<max;){
                begin--;
                sum+=arr[begin];
            }
            System.out.printf("%d %d %d\n", max, arr[begin], arr[idx]);
        }
    }
}

发表于 2018-03-02 17:50:33 回复(0)
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
	int k;
	while(scanf("%d",&k)!=EOF){
		if(k==0)
			break;
		vector<int> list(k,0);
		for(int i=0;i<k;i++){
			scanf("%d",&list[i]);
		}
		vector<int> myList=list;
		sort(myList.begin(),myList.end());
		if(myList[myList.size()-1]<0){
			printf("%d %d %d\n",0,list[0],list[k-1]);
		}else if(myList[myList.size()-1]==0){
			printf("%d %d %d\n",0,0,0);
		}else{
			int numMax=0;
			int start=0,end=0;
			int currentStart=0;
			int result=0;
			for(int i=0;i<k;i++){
				if((numMax+list[i])<list[i]){
					currentStart=i;
				}
				numMax=max(numMax+list[i],list[i]);
				if(result<numMax){
					start=currentStart;
					end=i;
					result=numMax;            
				}
			}
			printf("%d %d %d\n",result,list[start],list[end]);
		}
	}
	return 0;
}

发表于 2016-10-28 22:11:46 回复(0)
#include<stdio.h>
(737)#include<stdint.h>

/* 
    最大连续子序列

    首先是正常的最大连续子序列的一个动态规划问题
    dp[i] = max(arr[i], dp[i-1] + arr[i])
    我们只需要保存最大的那个值的结束的位置
    然后我们从结束的位置从后往前遍历,找到第一个 dp[i] 大于 0 的位置即可
    (此处的操作是从后往前找到第一个 dp[i] 小于 0 的数字,如果全部都大于 0,我们就取到了第一个数字的位置


 */
#define MAXN 10000

int arr[MAXN];
int dp[MAXN];

int max(int a, int b) {
    return a > b ? a : b;
}

void MaxSequence(int k) {
    int maxVal = -1 * MAXN;     // 记录最大值
    int start = 0, end = 0; // 记录开始和结束位置的下标,初始为最大值,只要有比这个小的就保存
    for (int i = 0; i < k; i++)
    {
        if(i == 0) {
            start = 0;
            dp[i] = arr[i];
        }else {
            dp[i] = max(arr[i], arr[i] + dp[i-1]);
        }
        if(dp[i] > maxVal) {
            // 如果当前值大于最大值,那我们记录下末尾的值
            end = i;
        }
        maxVal = max(dp[i], maxVal);
    }
    int flag = 0;   // 看能否找到小于 0 的数字
    for (int i = end; i >= 0; i--)
    {   // 从后往前遍历,找到第一个小于0的dp[i],如果没有的话,那么就找到了第一个
        if(dp[i] < 0) {
            start = i;
            flag = 1;
            break;
        }
    }
    if(flag == 1) { // 找到了小于 0 的数字,那么往后看一个
        start += 1;
    }
    printf("%d %d %d\n", maxVal, arr[start], arr[end]);
}

int LessThanZero(int k) {
    for (int i = 0; i < k; i++)
    {
        if(arr[i] >= 0) {
            // 只要有一个大于等于0的,那么就不是这种情况了
            return 1;
        }
    }
    // 全部都小于0
    return 0;
}

int main()
{
    freopen("data.txt","r", stdin);
    int k;
    while (scanf("%d", &k) != EOF)
    {
        if(k == 0)
            break;
        for (int i = 0; i < k; i++)
        {
            scanf("%d", &arr[i]);
        }
        if(LessThanZero(k) == 0) {
            // 如果全部小于 0,那么输出 0 和首尾数字
            printf("0 %d %d\n", arr[0], arr[k-1]);
        }else {
            MaxSequence(k);
        }
    }
    
    return 0;
}

发表于 2020-03-04 22:03:25 回复(0)
def solution(num_list):
    s, max_s = 0, 0
    i_start, i_end, i_temp = 0, 0, 0
    for i, num in enumerate(num_list):
        s += num
        if s > max_s:
            i_end = i
            i_start = i_temp
            max_s = s
        if s < 0:
            s = 0
            i_temp = i + 1
    if i_start == i_end and i_start == 0:
        print(max_s, num_list[0], num_list[-1])
    else:
        print(max_s, num_list[i_start], num_list[i_end])

def main():
    K = int(input())
    inputs = list(map(int, input().split()[:K]))
    solution(inputs)

if __name__ == '__main__':
    main()
发表于 2018-12-09 00:11:32 回复(0)
动态规划的思想去做,但是牛客网感觉测试用例不对(卡在70%),我在本地都是正确的,测试用例结果就不一样,有没有遇到一样情况的?

#include<iostream>

#include<stdio.h>

#include<string>

using namespace std;


void handle(int *inputs,int N)

{

    int *dp = new int[N];

    int firstId[100001];


    dp[0] = inputs[0];

    for(int i=0;i<N;i++)

    {

        int a = inputs[i];

        int b = dp[i-1]+inputs[i];

        

        if(a>b)

        {

            dp[i] = a;

            firstId[i]=1;

        }

        else

        {

            dp[i] =b;

            firstId[i]=0;

        }

    }

    int max = dp[0];

    int lastid=0;

    for(int i=0;i<N;i++)

    {

        if(dp[i]>max)

        {

            max=dp[i];

            lastid = i;

        }

    }

    

    int firstid =  lastid;

    for(int i=lastid;i>=0;i--)

    {

        if(firstId[i]==1)

        {

            firstid = i;

            break;

        }


    }

    if(max<0)

    {

        max=0;

        lastid = N-1;

        firstid = 0;

    }

    cout<<max<<" "<<inputs[firstid]<<" "<<inputs[lastid]<<endl;


}


int main()

{

    while(1)

    {

        int N = 0;

        scanf("%d",&N);

        if(N==0)

            break;

        int *inputs = new int[N];

        for(int i=0;i<N;i++)

        {

            scanf("%d",&inputs[i]);

        }

        handle(inputs,N);

        //cout<<inputs[0];

    }

    return 0;

}


发表于 2018-02-20 22:37:44 回复(0)

利用的是求连续最大子序列和的办法:
(1)当前面最大子序列和为负数的时候,后面的加上其一定会比后面本身更小,所以把sum置为0,重新寻找连续最大子序列和
(2)重新寻找的时候,也就是新序列开始的时候,记录下此时的数,可能是最大连续子序列和的开始数
(3)当新的连续最大子序列和大于之前的,说明之前的子序列不是所求,则更新序列的开始数和结尾数

#include <iostream>
using namespace std;

int main()
{
    int sum, K, max;
    while(cin>>K)
    {
        if(K==0) break;
        sum = 0, max = 0;
        int nstart, start, nend, first, last;
        cin>>nstart;
        first = last = start =  max = sum = nend = nstart;
        for(int i = 1; i<K; i++)
        {
            int tmp;
            cin>>tmp;
            if(sum<0){  //重新寻找最大连续子序列和
                sum = 0;
                start = tmp;  //记录序列的开始数
            }
            sum+=tmp;
            if(sum>max){  //当找到更大的连续子序列和,更新序列的开始和结尾
                max = sum;
                nstart = start;
                nend = tmp;
            }
            if(i==K-1) last = tmp;
        }
        if(max<0)  //当所有的数都是负数的时候,最大的和一定为负
            cout<<0<<" "<<first<<" "<<last<<endl;
        else
            cout<<max<<" "<<nstart<<" "<<nend<<endl;
    }
    return 0;
}
发表于 2018-03-20 15:10:51 回复(1)
DP - 最大连续子序列和问题的变形
记dp[i] - 以元素ai(1<=i<=n)结尾的连续子序列的和,则有两种情况:
        ①这个最大和的连续子序列只有一个元素,即以a[i]开始,以a[i]结尾;
        ②这个最大和的连续子序列有多个元素,即从前面某处a[j]开始(j<i),一直到a[i]结尾。

对第一种情况,最大和即a[i]本身;

对第二种情况,最大和即dp[i-1]+a[i]。

于是得到状态转移方程:

 dp[i] = max{A[i], dp[i-1]+A[i]} (边界条件: dp[1]=a[1])

不过,这里要求判断输入全为负数的情况,并要求输出所求最大连续子序列的起点和终点元素,因此稍作处理即可,本质不变。
#include <stdio.h>
#define maxn 10010
int n,a[maxn];
struct DP{      //考察: 以第i个元素为终点的连续子序列
    int left;   //子序列起点
    int right;  //子序列终点
    int val;    //子序列和
} dp[maxn];
//判断输入是否均为负数
int Judge(int *a,int n){
    int i;
    for(i=1;i<=n;i++){
        if(a[i]>=0)
            return 0;
    }
    return 1;
}
int main(){
    int i;
    int maxLeft,maxRight,maxVal;  //记录最大连续子序列起点.终点.和
    while(scanf("%d",&n)!=EOF){
        if(n==0)
            break;
        for(i=1;i<=n;i++)
            scanf("%d",&a[i]);
        //输入数据均为负数, 则输出0及首尾元素
        if(Judge(a,n))
            printf("0 %d %d\n",a[1],a[n]);
        //否则, 递推
        else{
            dp[1].left=dp[1].right=1;
            dp[1].val=a[1];
            //考察a[i] 与 dp[i-1].val+a[i] 的大小关系
            for(i=2;i<=n;i++){
                //后者大, 说明在dp[i-1]的基础上追加a[i] 得到的连续子序列和更大
                if(a[i]<dp[i-1].val+a[i]){
                    dp[i].left=dp[i-1].left;
                    dp[i].right=i;
                    dp[i].val=dp[i-1].val+a[i];
                }
                //前者大, 说明此时a[i]独自成为一个连续子序列
                else{
                    dp[i].left=i;
                    dp[i].right=i;
                    dp[i].val=a[i];
                }
            }
            //在所有连续子序列中求解和最大的
            maxLeft=dp[1].left;
            maxRight=dp[1].right;
            maxVal=dp[1].val;
            for(i=2;i<=n;i++){
                if(dp[i].val>maxVal){
                    maxVal=dp[i].val;
                    maxLeft=dp[i].left;
                    maxRight=dp[i].right;
                }
            }
            printf("%d %d %d\n",maxVal,a[maxLeft],a[maxRight]);
        }
    }
    return 0;
}

发表于 2019-01-22 09:10:30 回复(1)
#include<stdio.h>
#define max(a,b) a>b?a:b
int a[10005],Sum[10005];
int main(){
    int n,i,Max,sum,flag,f,l,last;
    while(scanf("%d",&n)!=EOF&&n){
        sum=0,Max=-999999999,flag=1;
        for(i=1;i<=n;i++){
            scanf("%d",&a[i]);
            if(a[i]>=0) flag=0;
            sum=max(sum+a[i],a[i]);
            if(Max<sum){
                Max=sum;
                last=i;
            }
            Sum[i]=a[i]+Sum[i-1];
        }
        if(flag==1) printf("0 %d %d\n",a[1],a[n]);
        else{
            for(i=0;i<=n;i++)
                if(Sum[last]-Sum[i]==Max) break;
            printf("%d %d %d\n",Max,a[i+1],a[last]);
        }
    }
}

发表于 2017-10-16 22:51:45 回复(1)
暴力解
#include <stdio.h>
#include <algorithm>
using namespace std;
int max(int a,int b){
    return a>b?a:b;
}
struct E{
    int max;
    int start;
    int end;
}dp[10001];
bool cmp(E a,E b){
    return a.max>b.max;
}
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        int num[10001];
        for(int i=0;i<n;i++){
            scanf("%d",&num[i]); 
        }
        for(int i=0;i<n;i++){
            dp[i].start=i;
            dp[i].end=i;
            dp[i].max=num[i];
            int sum=num[i];
            for(int j=i+1;j<n;j++){
                sum+=num[j];
                if(sum>dp[i].max){
                    dp[i].max=sum;
                    dp[i].end=j;
                }
            }
        }
        sort(dp,dp+n,cmp);
        printf("%d %d %d\n",dp[0].max,num[dp[0].start],num[dp[0].end]);
    }
    return 0;
}

发表于 2018-02-17 14:02:52 回复(0)