Given a sequence of K integers { N1
, N2
, ..., NK
}. A continuous subsequence is defined to be { Ni
, Ni+1
, ..., Nj
} where 1 <= i <= j <= K. The Maximum Subsequence
is the continuous subsequence which has the largest sum of its
elements. For example, given sequence { -2, 11, -4, 13, -5, -2 }, its
maximum subsequence is { 11, -4, 13 } with the largest sum being 20.
Now you are supposed to find the largest sum, together with the first
and the last numbers of the maximum subsequence.
[编程题]Maximum Subsequence Sum (25)
- 热度指数：5510 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
输入描述:
Each input file contains one test case. Each case occupies two lines. The first line contains a positive integer K (<= 10000). The second line contains K numbers, separated by a space.
输出描述:
For each test case, output in one line the largest sum, together with the first and the last numbers of the maximum subsequence. The numbers must be separated by one space, but there must be no extra space at the end of a line. In case that the maximum subsequence is not unique, output the one with the smallest indices i and j (as shown by the sample case). If all the K numbers are negative, then its maximum sum is defined to be 0, and you are supposed to output the first and the last numbers of the whole sequence.
示例1
输入
10<br/>-10 1 2 3 4 -5 -23 3 7 -21
输出
10 1 4
/*pat 牛客都AC了；牛客AC，但pat一个测试点无法通过，注意此case： 4 -2 0 0 -1 输出：0 0 0 */ #include <iostream> using namespace std; const int maxn=10001; int a[maxn],dp[maxn]; int main() { int n,flag=0,m,start,end,s,e; cin>>n; for(int i=0;i<n;i++) { cin>>a[i]; if(a[i]>=0) flag=1; } if(flag==0) { cout<<0<<" "<<a[0]<<" "<<a[n-1]<<endl; return 0; } m=dp[0]=a[0]; start=end=s=e=0; for(int i=1;i<n;i++) { if(a[i]>(dp[i-1]+a[i])) { dp[i]=a[i]; s=e=i; } else { dp[i]=dp[i-1]+a[i]; e=i; } if(m<dp[i]) { m=dp[i]; start=s; end=e; } } cout<<m<<" "<<a[start]<<" "<<a[end]<<endl; return 0; }
编辑于 2018-03-02 15:51:27
回复(5)
牛客可以通过，PAT只通过90%，求大神告知原因
import java.util.Scanner; /**
* 1007. Maximum Subsequence Sum (25)
*
* @author Jacob
* 注意：认真阅读题目，输出格式为：最大和序列 序列第一个数字（不是下标） 序列最后一个数字（不是下标）
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[] arr = new int[N];
for (int i = 0; i < N; i++)
arr[i] = sc.nextInt();
int max = Integer.MIN_VALUE, maxBegin = 0, maxEnd = 0;
int sum = 0, tmpBegin = 0, tmpEnd = 0;
for (int i = 0; i < N; i++) {
if (sum < 0) {
sum = 0;
tmpBegin = arr[i];
}
sum += arr[i];
tmpEnd = arr[i];
if (sum > max) {
max = sum;
maxBegin = tmpBegin;
maxEnd = tmpEnd;
}
}
if (max >= 0)
System.out.println(max + " " + maxBegin + " " + maxEnd);
else//结果小于0特殊处理
System.out.println(0 + " " + arr[0] + " " + arr[N - 1]);
sc.close();
}
}
编辑于 2017-08-26 11:25:11
回复(3)
输出的是最大连续子数列和，以及起始的数字和终结的数字；
这里有个坑就是，数组中的某两段连接着的最大连续子数列和可能相加等于0，而对于整个数组的最大连续子数列又是与这两端连在一起且在其后面，也就是说，最后要求输出的最大连续子数列是必须加上这两段的，而子数列和不变。
#include <iostream>
#include <vector>
using namespace std;
void MAXsum(vector<int> data, int length)
{
int Cursum = 0, Maxsum = 0;
int start = 0, end = 0;
for (int i = 0; i < length; i++)
{
Cursum += data[i];
if (Cursum < 0)
Cursum = 0;
if (Cursum > Maxsum)
{
Maxsum = Cursum;
end = i;
}
}
if (Maxsum == 0)
cout << 0 << " " << data[0] << " " << data[length - 1] << endl;
else
{
int sum = 0;
int j = end;
for (; j >= 0; j--)
{
sum += data[j];
if (sum == Maxsum)
{
start = j;
// break;
}
}
cout << Maxsum << " " << data[start] << " " << data[end] << endl;
}
}
int main()
{
int length;
while (cin >> length)
{
vector<int> data(length), res;
for (int i = 0; i < length; i++)
cin >> data[i];
MAXsum(data, length);
}
return 0;
}
发表于 2017-04-28 16:32:26
回复(0)
import java.util.Scanner;
//乍看一下好像很难，暴力求解似乎要o(n^2),但是鉴于k的个数范围以及nowcoder对于时间的要求不用想也知道会超时。
//仔细分析一下，一次遍历的话其实只有2种情况：
//①前面的和<0，那么当前数作为start重新开始一个序列吧！
//②前面的和>=0（由于求最小ij所以要带着等于号），
// 那么就判断：加上新数字的新总和newsum是否>存储着的之前的某次最大总和maxsum？
// 大于的话就把数据存储下来作为新的总和maxsum=newsum！
//用这种方法能确保maxsum是最大的！
//
public class Main {
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
int n=in.nextInt();
int a[]=new int[n];
for(int i=0;i<n;i++){
a[i]=in.nextInt();
}
int oldsum=a[0]; //前面所有数字的总和
int start=0; //序列第一个数字
int maxstart=0; //记录最大总和时候的开始数字
int end=0; //序列最末数字（同时也是最大总和时候的最末数字）
int newsum; //包含当前数字的新总和
int maxsum=Integer.MIN_VALUE; //用来记录最大总和
for(int i=1;i<n;i++){
if(oldsum<0){
start=a[i]; //当前数字作为序列第一个数啦
oldsum=0; //所以之前的总和清0咯
}
newsum=oldsum+a[i];
oldsum=newsum; //下一次遍历时候的oldsum就是这次的newsum
if(newsum>maxsum){ //更新并存储下最大和时候的数据
maxsum=newsum;
end=a[i];
maxstart=start;
}
}if(maxsum<0){
System.out.println(0+ " "+a[0]+" "+a[n-1]);
}else
System.out.println(maxsum+" "+maxstart+" "+end);
}
}
发表于 2016-10-28 17:42:52
回复(0)
一次循环完工，从前往后，完成四个任务，填写数列值a[i]、生成从头开始的累加值b[i]、记录从头以来的最小累加值所在处minb[i]、计算a[i]与此前最小累加值b[minb[i]]的差值，寻找最大差值。
#include<stdio.h>
int main()
{
int a[10001],b[10001],minb[10001],i,N,h=1,t,sum=0;
scanf("%d",&N);
t=N;
b[0]=minb[0]=0;
for(i=1;i<=N;i++){
scanf("%d",a+i);
b[i]=b[i-1]+a[i];
if(b[minb[i-1]]<=b[i]){
minb[i]=minb[i-1];
if(b[i]-b[minb[i]]>=sum){
h=minb[i]+1;
t=i;
sum=b[i]-b[minb[i]];
}
}
else minb[i]=i;
}
printf("%d %d %d",sum,a[h],a[t]);
}
编辑于 2019-12-25 21:28:13
回复(0)
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
int n;
cin>>n;
vector<int> v(n);
for(int i=0; i<n; ++i){
cin>>v[i];
}
int beg, end;
vector<int> dp(n); // dp[i] is max sum of subarray ending with v[i]
dp[0]=v[0], end=0;
for(int i=1; i<n; ++i){
dp[i] = max(dp[i-1]+v[i], v[i]);
if(dp[i]>dp[end]){
end = i;
}
}
int j, sum;
for(j=end, sum=0; j>=0; --j){
sum += v[j];
if(sum==dp[end]){
beg = j; // get the smallest j if duplicated
//break;
}
}
if(dp[end]<0){
cout<<0<<" "<<v[0]<<" "<<v[n-1]<<endl;
return 0;
}
cout<<dp[end]<<" "<<v[beg]<<" "<<v[end]<<endl;
return 0;
}
发表于 2018-02-20 15:59:34
回复(0)
没办法了！pat只有一个未通过，牛客网90%通过，但是测试用例写得不清楚，不知道什么原因。这里算法关键是 if(currentSum<0) break;，一旦求和<0，说明当前的子串一定不是最大的。这样可以避免超时。
#include<stdio.h>
#include<iostream>
#include<string>
using namespace std;
int main()
{
int sum,first,last;
int N = 0;
int input[10000];
scanf("%d",&N);
if(N==0)
{
cout<<"0 0 0"<<endl;
return 0;
}
for(int i=0;i<N;i++)
{
scanf("%d",&input[i]);
}
sum=input[0];
first = input[0];
last = input[0];
for(int i=0;i<N;i++)
{
int currentSum=0;
for(int j=i;j<N;j++)
{
//计算从input[i]计算到input[j]
currentSum+=input[j];
if(currentSum<0) break;
if(sum<currentSum)
{
sum = currentSum;
first = input[i];
last = input[j];
}
}
}
cout<<sum<<" "<<first<<" "<<last<<endl;
return 0;
}
发表于 2018-02-15 23:35:36
回复(1)
核心是一道经典的DP题
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int K = Integer.parseInt(br.readLine());
int[] nums = new int[K];
String[] input = br.readLine().split("\\s+");
int nonNegative = 0;
for (int i = 0; i < K; ++i) {
int tmp = Integer.parseInt(input[i]);
nums[i] = tmp;
if (tmp >= 0) {
nonNegative++;
}
}
input = null;
if (nonNegative == 0) {
System.out.format("%d %d %d\n", 0, nums[0], nums[K - 1]);
return;
}
int maxSum = nums[0];
int maxSumIndex = 0;
int maxSumLen = 1;
int preMaxSum = nums[0];
int preMaxSumLen = 1;
for (int i = 1; i < K; ++i) {
if (preMaxSum >= 0) {
preMaxSum += nums[i];
preMaxSumLen++;
} else {
preMaxSum = nums[i];
preMaxSumLen = 1;
}
if (nums[i] >= 0 && preMaxSum > maxSum) {
maxSum = preMaxSum;
maxSumIndex = i;
maxSumLen = preMaxSumLen;
}
}
System.out.format("%d %d %d\n", maxSum, nums[maxSumIndex - maxSumLen + 1], nums[maxSumIndex]);
}
}
发表于 2025-02-11 15:39:18
回复(0)
// Maximum Subsequence Sum
#include <stdio.h>
int main()
{
int num[10001];
int i,begin,end,begin0;
int max_S,sum,n;
sum = 0;
max_S = 0;
begin0 = 0;
begin =0;
scanf("%d",&n);
end = n-1;
for (i = 0;i < n; i++)
{
scanf("%d",&num[i]);
}
for (i = 0;i < n; i++)
{
sum = sum + num[i];
if (sum > max_S)
{
max_S = sum;
end = i;
begin = begin0;
}
if (sum < 0)
{
sum = 0;
begin0 = i + 1;
}
}
printf("%d %d %d\n",max_S,num[begin],num[end]);
}
发表于 2021-07-27 17:25:17
回复(0)
//
// Created by 硬汉J on 2021/2/25.
// 全AC了，AC不了的，注意看题目，注意不要小于零
//
#include <iostream>
#include <vector>
using namespace std;
int main(){
int n;
cin >> n;
vector<int> initial(n);
for (int i = 0; i < n; ++i) {
cin >> initial[i];
}
vector<int> dp(n);
dp[0] = initial[0];
int end = 0;
for (int i = 1; i < n; ++i) {
dp[i] = max(dp[i - 1] + initial[i], initial[i]);
if (dp[i] > dp[end]) {
end = i;
}
}
int j;
int beg = 0;
int sum;
for (j = end, sum = 0; j >= 0; j--) {
sum += initial[j];
if (sum == dp[end]) {
beg = j;
}
}
if (dp[end] < 0) {
cout << 0 << " " << initial[beg] << " " << initial[n - 1] << endl;
} else {
cout << dp[end] << " " << initial[beg] << " " << initial[end] << endl;
}
return 0;
}
发表于 2021-02-25 18:51:16
回复(0)
#include<iostream>
#include<vector>
using namespace std;
vector<int>myvect;
vector<int>dp(10000);
int main()
{
int n;
bool flag = false; //判断是否有非负数
cin >> n;
for (int i = 0; i < n; i++)
{
int a;
cin >> a;
if (a >= 0)
flag = true;
myvect.push_back(a);
}
if (flag == false)
{
cout << 0 << " " << myvect[0] << " " << myvect[n - 1] << endl;
}
else
{
//计算末端
dp[0] = myvect[0];
for (int i = 1; i < n; i++)
{
dp[i] = max(dp[i - 1] + myvect[i], myvect[i]);
}
int right = 0;
for (int i = 1; i < n; i++)
{
if (dp[right] < dp[i])
right = i;
}
int res = dp[right]; //保存最大值
//计算始端
dp[n - 1] = myvect[n - 1];
for (int i = n - 2; i >= 0; i--)
{
dp[i] = max(dp[i + 1] + myvect[i], myvect[i]);
}
int left = 0;
for (int i = 1; i < n; i++)
{
if (dp[left] < dp[i])
left = i;
}
cout << res << " " << myvect[left] << " " << myvect[right] << endl;
}
}
发表于 2020-09-28 09:06:33
回复(0)
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 10001;
int k, right, sum=-99999;
int num[maxn];
int dp[maxn], left[maxn]={0};
bool flag = false;
int main(void) {
scanf("%d", &k);
for(int i=0;i<k;++i){
scanf("%d", &num[i]);
if(num[i]>=0) flag = true;
}
if(flag==false){
printf("%d %d %d\n", 0, num[0], num[k-1]);
return 0;
}
right = k-1;
dp[0] = num[0];
for(int i=1;i<k;++i){
dp[i] = max(num[i], dp[i-1]+num[i]);
if(dp[i]>sum) {
sum = dp[i];
right = i;
}
if(num[i]>(dp[i-1]+num[i])) left[i] = i;
else left[i] = left[i-1];
}
printf("%d %d %d\n", sum, num[left[right]], num[right]);
return 0;
}牛客AC,但是PAT3号测例过不去,郁闷....
发表于 2020-07-12 10:54:41
回复(0)
//状态方程 dp[i]=max(dp[i-1]+A[i],A[i])//
//###################################//
#include<cstdio>
const int maxn=10010;
int dp[maxn][2]; //dp[i][0]记录最大连续子序列；dp[i][1]记录前端点;
int A[maxn]; //数组
int main()
{
int k=0,num=0; //k数组个数，num负数个数
scanf("%d",&k);
for(int i=0;i<k;i++) //输入
{
scanf("%d",A+i);
if(A[i]<0) num++;
}
if(num==k)
{
printf("%d %d %d\n",0,A[0],A[k-1]);
return 0;
}
dp[0][0]=A[0]; //边界条件
dp[0][1]=0;
int max=0; //记录最大子序列后端下标;
for(int i=1;i<k;i++)
{
if(A[i]>dp[i-1][0]+A[i])
{
dp[i][0]=A[i];
dp[i][1]=i;
}
else
{
dp[i][0]=A[i]+dp[i-1][0];
dp[i][1]=dp[i-1][1];
}
if(dp[i][0]>dp[max][0]) //求最大子序列后端下标
max=i;
}
printf("%d %d %d\n",dp[max][0],A[dp[max][1]],A[max]);
return 0;
}
发表于 2020-03-26 10:08:57
回复(0)
#include <iostream>
using namespace std;
int main(){ int K; //数组个数 cin >> K; int *a = new int [K]; //动态创建数组 int t=-1; for (int i=0; i<K; i++) { cin>>a[i]; //输入数组 if ((t==-1)&&(a[i]>=0)) { t=i; //记录第一次出现正数的下标 } } int sum=0, MaxSum=0, left=t, right=t, mayLeft=t; if (t==-1) { //如果都是负数，则直接默认最大和为0，输出首尾 left = 0; right = K-1; } else { for (int i=t; i<K; i++) { sum += a[i]; if (sum>MaxSum) { //更新最大子列 MaxSum = sum; left = mayLeft; right = i; } else if (sum<0) { //若和为负数，则将前面所有舍弃, 可能的最大子列左下标更新为i+1 mayLeft = i+1; sum = 0; } } } //输出 cout<<MaxSum<<' '<<a[left]<<' '<<a[right]; delete[] a; return 0;
}
PAT和牛客均通过了
发表于 2019-02-01 13:39:58
回复(0)
#include<iostream>
using namespace std;
//1007 Maximum Subsequence Sum
//最大子列和问题
//需考虑全负数时，输出整个数列首与尾
int main() {
int k; //k<10^4
int temp, summ = 0, first, last; //中间变量
int maxsum = -1;
pair<int, int> answer={-1,-1};
int top, end,flag=0; //记录首尾与全负数
cin >> k;
cin >> first;
summ = last = top =end = first;
//第一个数是负数也没事，后续如果有正数一定会覆盖
//后续如果没有正数，flag会帮忙输出正确答案
maxsum = summ;
answer = { first,last };
if (first >= 0) flag = 1; //缺了这个判断过不了pat.3，一个正数的case
for (int i = 0; i<k - 1; ++i) {
cin >> temp;
if (summ<0) {//丢弃左边
first = last = temp;
summ = temp;
}
else{ //summ>=0
summ += temp; last = temp;
}
if (summ > maxsum) {//存在多种相同最大和时，取下标最小的
maxsum = summ;
answer = { first,last };
}
if (i == k - 2) end = temp; //存队尾
if (temp >= 0) flag = 1;
}
//考虑全负数
if(flag==0)
cout<<"0 "<<top<<" "<<end;
else
cout << maxsum << " " << answer.first << " " << answer.second;
return 0;
}
using namespace std;
//1007 Maximum Subsequence Sum
//最大子列和问题
//需考虑全负数时，输出整个数列首与尾
int main() {
int k; //k<10^4
int temp, summ = 0, first, last; //中间变量
int maxsum = -1;
pair<int, int> answer={-1,-1};
int top, end,flag=0; //记录首尾与全负数
cin >> k;
cin >> first;
summ = last = top =end = first;
//第一个数是负数也没事，后续如果有正数一定会覆盖
//后续如果没有正数，flag会帮忙输出正确答案
maxsum = summ;
answer = { first,last };
if (first >= 0) flag = 1; //缺了这个判断过不了pat.3，一个正数的case
for (int i = 0; i<k - 1; ++i) {
cin >> temp;
if (summ<0) {//丢弃左边
first = last = temp;
summ = temp;
}
else{ //summ>=0
summ += temp; last = temp;
}
if (summ > maxsum) {//存在多种相同最大和时，取下标最小的
maxsum = summ;
answer = { first,last };
}
if (i == k - 2) end = temp; //存队尾
if (temp >= 0) flag = 1;
}
//考虑全负数
if(flag==0)
cout<<"0 "<<top<<" "<<end;
else
cout << maxsum << " " << answer.first << " " << answer.second;
return 0;
}
编辑于 2019-01-13 14:00:56
回复(0)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
private static int N;
private static int[] sum;
private static int[] start;
private static int[] a;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str;
String[] strs;
while((str=br.readLine())!=null) {
//read data
N = Integer.valueOf(str);
sum = new int[N];
start = new int[N];
a = new int[N];
strs = br.readLine().split(" ");
for(int i=0; i<N; i++) {
a[i] = Integer.valueOf(strs[i]);
}
//init
sum[0] = a[0];
start[0] = 0;
//iterative
for (int i = 1; i < N; i++) {
if (sum[i - 1] > 0) {
sum[i] = sum[i - 1] + a[i];
start[i] = start[i - 1];
} else {
sum[i] = a[i];
start[i] = i;
}
}
//reconstruction solution
int max = Integer.MIN_VALUE;
int index = 0;
for (int i = 0; i < N; i++) {
if (max < sum[i]) {
max = sum[i];
index = i;
}
}
if (max < 0) {
System.out.println(0 + " " + a[0] + " " + a[N - 1]);
} else {
System.out.println(max + " " + a[start[index]] + " " + a[index]);
}
}
}
}
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
private static int N;
private static int[] sum;
private static int[] start;
private static int[] a;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str;
String[] strs;
while((str=br.readLine())!=null) {
//read data
N = Integer.valueOf(str);
sum = new int[N];
start = new int[N];
a = new int[N];
strs = br.readLine().split(" ");
for(int i=0; i<N; i++) {
a[i] = Integer.valueOf(strs[i]);
}
//init
sum[0] = a[0];
start[0] = 0;
//iterative
for (int i = 1; i < N; i++) {
if (sum[i - 1] > 0) {
sum[i] = sum[i - 1] + a[i];
start[i] = start[i - 1];
} else {
sum[i] = a[i];
start[i] = i;
}
}
//reconstruction solution
int max = Integer.MIN_VALUE;
int index = 0;
for (int i = 0; i < N; i++) {
if (max < sum[i]) {
max = sum[i];
index = i;
}
}
if (max < 0) {
System.out.println(0 + " " + a[0] + " " + a[N - 1]);
} else {
System.out.println(max + " " + a[start[index]] + " " + a[index]);
}
}
}
}
为什么牛客有两个case没过，它也没给全我没过的case，不知道哪里出现问题，PAT都过了
发表于 2018-09-26 17:26:27
回复(0)
思路：用两个结构体保存对比。
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
struct rlt
{
int sumMax;
int startNum;
int endNum;
};
struct rlt FindMaxSubSquence(const vector<int> &v)
{
struct rlt temp;
struct rlt max;
temp.startNum = v[0];
temp.endNum = v[0];
temp.sumMax = v[0];
max = temp;
for (int i = 1; i < v.size(); i++)
{
if (v[i] >= 0 && v[i - 1] > 0)
{
temp.endNum = v[i];
temp.sumMax += v[i];
if (temp.sumMax > max.sumMax)
{
max = temp;
//cout << temp.startNum << " temp.startNum " << temp.endNum << " " << temp.sumMax << endl;
}
}
else if (v[i] >= 0 && v[i - 1] <= 0)
{
if(temp.sumMax >= 0)
{
temp.endNum = v[i];
temp.sumMax += v[i];
if (temp.sumMax > max.sumMax)
{
max = temp;
//cout << temp.startNum << " temp.startNum " << temp.endNum << " " << temp.sumMax << endl;
}
}
else if(temp.sumMax < 0)
{
temp.sumMax = v[i];
temp.startNum = v[i];
temp.endNum = v[i];
if (temp.sumMax > max.sumMax)
{
max = temp;
}
}
}
else if (v[i] < 0)
{
temp.sumMax += v[i];
temp.endNum = v[i];
if (temp.sumMax > max.sumMax)
{
max = temp;
}
}
}
return max;
}
int main()
{
//ifstream cin("test.txt");
int n;
while (cin >> n)
{
vector<int> v(n);
bool negative = true;
for (int i = 0; i < n; i++)
{
cin >> v[i];
if (v[i] >= 0)
{
negative = false;
}
}
if (negative)
{
cout << 0 << " " << v[0] << " " << v[v.size() - 1] << endl;
continue;
}
struct rlt max = FindMaxSubSquence(v);
cout << max.sumMax << " " << max.startNum << " " << max.endNum << endl;
}
system("pause");
}
发表于 2018-08-19 09:29:35
回复(0)
import java.util.Scanner;public class Main {
public static int judge(int a[])
{
int flag = 0;
for(int i = 0; i < a.length; i++)
{
if(a[i] >= 0)
{
flag = 1;
break;
}
}
if(flag == 0)
return 0;
return 1;
}
/* public static int maxsum_fenzhi(int a[], int left, int right)
{
if(left == right)
return a[left] > 0 ? a[left]: 0;
else
{
int leftsum = maxsum_fenzhi(a, left, (left + right)/ 2);
int rightsum = maxsum_fenzhi(a, (left + right)/ 2 + 1, right);
int s1 = 0, s2 = 0, lefts = 0, rights = 0;
for(int i = (left + right)/ 2; i >= left ; i--)
{
lefts += a[i];
if(lefts > s1)
s1 =lefts;
}
for(int j = (left + right)/ 2 + 1 ; j <= right ; j++)
{
rights += a[j];
if(rights > s2)
s2 =rights;
}
int maxsum = s1 + s2;
if(maxsum < leftsum)
maxsum = leftsum;
if(maxsum < rightsum)
maxsum = rightsum;
//System.out.print(maxsum);
return maxsum;
}
}*/
/*public static void maxsum_qiongju(int a[], int left, int right)
{
int maxsum = 0, temp = 0;
int leftpos = 0, rightpos = 0;
for(int i = left; i < right; i++)
{
//System.out.print("x:");
for(int j = i; j < right; j++)
{
temp = 0;
for(int k = i; k <= j; k++)
temp += a[k];
if(maxsum < temp)
{
//System.out.println(temp + " " + a[leftpos] + " " + a[rightpos]);
maxsum = temp;
leftpos = i;
rightpos = j;
}
}
}
System.out.print(maxsum + " " + a[leftpos] + " " + a[rightpos]);
}*/
public static void maxsum_dongtaiguihua(int a[])
{
int b = 0, maxsum = 0, leftpos = 0, rightpos = 0, pos = 0;
int i = 0;
for(i = 0; i < a.length; i++)
{
if(b > 0)
{
b = b + a[i];
//rightpos ++;
}
else
{
b = a[i];
pos = i;
}
if(b > maxsum)
{
maxsum = b;
rightpos = i;
leftpos = pos;
}
if(b == 0 && maxsum == 0)
{
rightpos = i;
leftpos = pos;
}
}
System.out.print(maxsum + " " + a[leftpos] + " " + a[rightpos]);
}
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
int count = sc.nextInt();
int[] a = new int[count];
for(int i = 0; i < count; i++)
a[i] = sc.nextInt();
if(judge(a) == 0)
System.out.println(0 + " " + a[0] + " " + a[a.length - 1]);
else
{
//System.out.println(maxsum_fenzhi(a, 0, a.length - 1));
//maxsum_qiongju(a, 0, a.length);
maxsum_dongtaiguihua(a);
}
}
}
发表于 2018-08-12 16:07:03
回复(0)
问题信息
难度：
25条回答
13收藏
9031浏览
通过挑战的用户
-
2023-02-23 01:01:23 -
2023-02-22 14:17:11
-
2023-02-22 13:49:21 -
2023-02-21 10:38:51 -
2023-02-18 19:16:30
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
