洛谷 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记录最大的值
			else
				sum=t;
			result=Math.max(result, sum);
		}
		pw.print(result);
		pw.flush();
	}
}