最大连续子序列

//写一点功能就先测试一下
#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;
}

#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;
}

#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);	
	
} 

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]);
        }
    }
}

#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;
}

#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;
}

///方法一:只保存最后一个下标以及最大和   然后通过最大和和最后一个下标计算出第一个
#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;
}

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]);
        }
    }
}

#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;
}

#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;
}

利用的是求连续最大子序列和的办法：
（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;
}

#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]);
        }
    }
}

#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;
}

#include <bits/stdc++.h>
using namespace std;

struct Dp{        //建立一个状态三元组dp用来记录当前最大子序列和的起始位置，结束位置，值(left, right, val)
    int left;
    int right;
    int val;
};

const int MAXN = 10001;
int arr[MAXN];
Dp dp[MAXN];

int MaxSubsequence(int k){
    int maxval = 0;
    for(int i = 0; i < k; ++i){
        if(i == 0){
            dp[i].val = arr[i];    //初始化
            dp[i].left = 0;
            dp[i].right = 0;
        }
        else{
           // dp[i].val = max(arr[i], dp[i-1].val + arr[i]);
            if(arr[i] < dp[i-1].val + arr[i]){        //状态转移方程，如果当前arr[i]比之前的最大子序列和加上自身要小
                dp[i].left = dp[i-1].left;        //那么dp[i].left就等于dp[i-1].left，依次类推到最左边
                dp[i].right = i;                  //dp[i].right不断更新，到最大的位置，也就是这个子序列的最右边
                dp[i].val = dp[i-1].val + arr[i];    //值为最大值
            }
            else{
                dp[i].left = i;        //相对的，如果arr[i]比之前的最大子序列和加上自身要大，那么就要重新开始统计一个子序列
                dp[i].right = i;       //左右下标都更新为当前下标
                dp[i].val = arr[i];    //值为当前值arr[i]，也就是最大值
            }
        }
        //maxval = max(maxval, dp[i]);
        if(maxval < dp[i].val){
            maxval = dp[i].val;   //dp[i].val存储的是到arr[i]的最大子序列和，maxval用来记录整个arr数组的最大子序列和
        }
    }
    return maxval;
}

int main(){
    int k;
    while(cin >> k && k){
        bool flag = false;
        for(int i = 0; i < k; ++i){
            cin >> arr[i];
            if(arr[i] >= 0){
                flag = true;
            }
        }
       if(!flag){
           cout << "0 " << arr[0] << " " << arr[k-1] << endl;
       }
       else{
            int ans = MaxSubsequence(k);
            for(int i = 0; i < k; ++i){        //遍历dp数组，如果找到ans的位置，根据对应的dp状态输出arr[]中的值
                if(ans == dp[i].val){
                    cout << ans << " " << arr[dp[i].left] << " " << arr[dp[i].right] << endl;
                    break;
                }
            }
       }
    }
    return 0;
}

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Solution24 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt();
            int[] arr = new int[n];
            for(int i=0; i<n; i++) {
                arr[i]=in.nextInt();
            }
            List<Integer> result = MaxSubArray(arr);
            for (int i = 0; i < result.size(); i++) {
                System.out.print(result.get(i));
                if (i + 1 < result.size()) {
                    System.out.print(" ");
                }
            }
        }
    }

    public static List<Integer> MaxSubArray(int[] arr) {
        List<Integer> result = new ArrayList<>();
        int start = 0;
        int end = -1;
        int curSum = 0;
        int maxSum = arr[0];
        while (start < arr.length) {
            if (end + 1 < arr.length && arr[end + 1] <= curSum + arr[end + 1]) {
                curSum += arr[++end];
            } else {
                curSum -= arr[start++];
            }
            if (curSum > maxSum) {
                result.clear();
                maxSum = curSum;
                result.add(maxSum);
                result.add(arr[start]);
                result.add(arr[end]);
            }

        }
        return result;
    }
}