洛谷 P1115 最大子段和 Java实现 前缀和基础

题目描述

给出一个长度为 n 的序列 a，选出其中连续且非空的一段使得这段和最大。

输入格式
第一行是一个整数，表示序列的长度 n。

第二行有 n个整数，第 i 个整数表示序列的第 i个数字 a_i

输出格式
输出一行一个整数表示答案。

题目详细:P1115 最大子段和

思路：前缀和

不光是前缀和，有一些dp的思想。先求出前缀和sum，然后我们从头开始遍历。代码中min_q代表着当前位置中最小的前缀和。这里有个绕的地方就是min_q可能0或者是负数两种情况。下面我们来分别讨论：

1. 当min_q为0时，这种情况也就是当前位置之前的所有的前缀和都是正数，注意的是前缀和是正数。比如 50,100，-1,100，虽然数组中有负数但是前缀和sum是正数，min_q肯定为0。啥意思呢，题目不是问最大子段和吗，当前位置之前的子段和是正数，你应该算入子段和中。
2. 当min_q为负数时，也就代表前面有一子段和是负数。那么当前最大子段和也就是当前的前缀和qz[i]-min_q，意思是舍去那些负的子段。

整体运用贪心的思想舍去当前最小的子段和。
其中这个题有一个核心思想，求连续最大子段和。那么下面这种情况该怎么选呢：
-2 -10 100 -10 2 3 4，出现了负正负，也就是一个正数被负数夹在中间，那么这个正数到底要不要的问题。
运用前缀和正好是为了解决这个问题，我们要不要一个数只是根据是否能让总体的结果变大。100 -10 的前缀和是90是大于0的，那么这个100就要。100 -101 前缀和是-1，那么这个100就不要。

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
public class Main {public static void main(String[] args) throws IOException{StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));PrintWriter pw=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));in.nextToken();int n=(int)in.nval;int[] sum=new int[n+1];int result=0x80000000;for(int i=1;i<=n;i++){in.nextToken();sum[i]=sum[i-1]+(int)in.nval;}int min_q=Math.min(0, sum[1]);for(int i=2;i<=n;i++){result=Math.max(sum[i]-min_q,result);if(sum[i]<min_q)min_q=sum[i];}pw.print(result);pw.flush();}
}

其实这个题也可以不用前缀和计算，但是同样的思想，当前面的子段的和小于0的时候我们就舍弃。但是可能在舍弃的那一段中，就已经出现最大的子段和了，所以我们需要result纪录最大值。比如
-1 10 10 -30 1 2 3
首先-1舍去，然后直到记录sum为20，rusult为20，继续往后舍去1前面的子段，最后运行完sum的结果为6，result为20

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
public class Main{public static void main(String[] args) throws IOException{StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));PrintWriter pw=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));in.nextToken();int n=(int)in.nval;in.nextToken();int result=(int)in.nval;int sum=result;int t;for(int i=1;i<n;i++){in.nextToken();t=(int)in.nval;if(sum>0)sum+=t;   //这个值可能变小，所以我们需要用result记录最大的值elsesum=t;result=Math.max(result, sum);}pw.print(result);pw.flush();}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！