[编程题]最大连续子序列
- 热度指数：11191 时间限制：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)
//写一点功能就先测试一下
#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()
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)
问题信息
难度：
103条回答
147收藏
18570浏览
通过挑战的用户
查看代码-
2023-03-10 11:52:53
-
2023-03-06 16:34:56 -
2023-03-05 16:23:16
-
2023-03-05 11:44:25 -
2023-03-03 17:17:51
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
