Question (in Chinese): http://ac.jobdu.com/problem.php?pid=1372
Question Name: Greatest Sum Of Subarrays
Question Description: Given an integer array, find the non-empty subarray with the greatest sum. If there are multiple subarray with the same greatest sum, return the one with the smallest begin index. If there are multiple subarray with the same greatest sum and begin index, return the one with the smallest end index.
Input: the input might contain multiple test cases. Each test case contains two lines. The first line includes one integers N (1 <= K <= N <= 100000). The second line includes N integers as the input array.
Output: For each test case, print one line with three integers: the sum, the begin index, and the end index.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | Input #1: 3 -1 -3 -2 5 -8 3 2 0 5 8 6 -3 -2 7 -15 1 2 2 Output #1: -1 0 0 10 1 4 8 0 3 Input #2: 4 -1 -2 0 5 4 1 -1 1 8 4 -1 -2 0 5 4 0 2 0 0 Output #2: 5 2 3 9 0 3 5 2 3 2 0 1 |
The solution is:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 | /*---------------------------------------------------------------- * Author: Sheng Yu codesays.com * Written: 08/28/2014 * Last updated: 08/28/2014 * * Filename: GreatestSumOfSubarrays.java * Compilation: javac GreatestSumOfSubarrays.java * Execution: java GreatestSumOfSubarrays * JDK Used: 1.7 *----------------------------------------------------------------*/ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; /** * A utility to find the consecutive sub-array with the greatest sum. * @author Sheng Yu codesays.com */ public class GreatestSumOfSubarrays { /** * Find the consecutive sub-array with the greatest sum in a given * array, and show its sum, begin position, and end position. * @param input the original array to find an sub-array. */ public void findSubarrayWithGreatestSum(int[] input) { int maxSoFar = Integer.MIN_VALUE; int begin = 0; int end = 0; int maxEndingHere = 0; int maxEndingHereBegin = 0; for (int i = 0; i < input.length; ++i) { // Find the max sum of any sub-array, which is ending here. if (maxEndingHere < 0) { maxEndingHere = input[i]; maxEndingHereBegin = i; } else { maxEndingHere += input[i]; } // Check whether we need to update the maxSoFar. // maxSoFar records the the sub-array with greatest sum globally. if (maxEndingHere > maxSoFar) { maxSoFar = maxEndingHere; begin = maxEndingHereBegin; end = i; } } System.out.printf("%d %d %dn", maxSoFar, begin, end); return; } /** * Stub for test. * @param args the command line arguments. * @throws IOException when input gets error. */ public static void main(String[] args) throws IOException { StreamTokenizer st = new StreamTokenizer(new BufferedReader( new InputStreamReader(System.in))); int inputSize = 0; int[] input = null; GreatestSumOfSubarrays finder = new GreatestSumOfSubarrays(); while (st.nextToken() != StreamTokenizer.TT_EOF) { // Get the next test case. inputSize = (int) st.nval; if (inputSize == 0) continue; input = new int[inputSize]; for (int i = 0; i < inputSize; ++i) { st.nextToken(); input[i] = (int) st.nval; } // Find the sub-array with the greatest sum. finder.findSubarrayWithGreatestSum(input); } } } |
First of all, thanks for sharing your solutions!
In the next time, could you please add the language name, remove the duplicate problem description, and add some essential comments?