题目

---

题目地址

思路

---

显然是最大子列和的进化版，那就先思考下经典的最大子列和。这也是道思维题，啥算法也没用到，全是思维技巧，真心不知道考试遇到这种题该怎么办了。

存放答案的一个类，我把它看成一个袋子，需要什么都可以“.”出来

class ans

{

	static int maxsub = 0;

	static int firstElement = 0;

	static int lastElement = 0;

	static int lastElementIndex = 0;

}

经典的最大子列和只是更新了maxsub，现在可以同时更新firstElement和lastElement，最后输出即可。

这时更新一下

		if (tempsum > ans.maxsub)

			{

				ans.lastElement = arr[i];

				ans.firstElement = firstElement;

				ans.maxsub = tempsum;

			}

以及

这时更新一下

	if (tempsum < 0)

			{

				if (i + 1 < arr.length)

					firstElement = arr[i + 1];

				tempsum = 0;

			}

对于为什么可以这样，我相信仔细思考一定能看懂。一定要先思考，再看答案，这样才能有共鸣。

代码

---

package 网易云数据结构;

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.io.OutputStreamWriter;

import java.io.PrintWriter;

import java.io.StreamTokenizer;

import java.security.acl.LastOwnerException;

import java.util.Scanner;

public class Main

{

	public static void main(String[] args) throws IOException

	{

		StreamTokenizer in = new StreamTokenizer(new BufferedReader(

				new InputStreamReader(System.in)));

		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

		in.nextToken();

		boolean isAllNegative = true;

		// 读入k个数据

		int k = (int) in.nval;

		int arr[] = new int[k + 1];

		for (int i = 1; i <= k; i++)

		{

			in.nextToken();

			arr[i] = (int) in.nval;

			if (arr[i] >= 0)

			{

				isAllNegative = false;

			}

		}

		// 处理数据

		int tempsum = 0;

		int firstElement = arr[1];

		for (int i = 1; i < arr.length; i++)

		{

			tempsum += arr[i];

			if (tempsum > ans.maxsub)

			{

				ans.lastElement = arr[i];

				ans.firstElement = firstElement;

				ans.maxsub = tempsum;

			}

			if (tempsum < 0)

			{

				if (i + 1 < arr.length)

					firstElement = arr[i + 1];

				tempsum = 0;

			}

		}

		// 输出

		if (isAllNegative)

		{

			System.out.println(0 + " " + arr[1] + " " + arr[arr.length - 1]);

		} else

			System.out.println(ans.maxsub + " " + ans.firstElement + " "

					+ ans.lastElement);

	}

}

class ans

{

	static int maxsub = 0;

	static int firstElement = 0;

	static int lastElement = 0;

	static int lastElementIndex = 0;

}