This article describes the Java implementation of the maximum value algorithm for finding the sum of sub-arrays. Share it for your reference, as follows:
Generally, C and C++ are used more frequently in algorithm implementation. Below we implement algorithms through Java language, which makes us feel more intimate.
topic:
Enter a shaping array, with positive and negative numbers in the array.
One or more consecutive integers in an array form a subarray, each subarray has a sum.
Find the maximum value of the sum of all subarrays.
For example, the input array is 1, -2, 3, 10, -4, 7, 2, -5, and the largest subarray is 3, 10, -4, 7, 2,
Therefore the output is the sum 18 of the subarray.
Implementation code:
package arrDemo;public class MaxSub { public static void main(String[] args) { // TODO automatic generated method stub findMaxSubArySum1(); } public static void findMaxSubArySum1() { // sum is the sum of the subarray int sum = 0; // max is the maximum sum of the subarray int max = 0; // start position of the maximum subarray int startPos = 0; // end position of the maximum subarray int endPos = 0; int[] array = { -1, 2, -3, 12, -5, -1, 9, -2 }; for (int i = 0; i < array.length; i++) { sum += array[i];// Sum if (sum < 0) {// If the current sum is found to be negative, clear it and the starting position starts from the next position sum = 0; startPos = i + 1; } if (sum > max) {// If the sum is found to be greater than the previous maximum, assign sum to max, and record the last position max = sum; endPos = i + 1; } } System.out.println("Wulin.com test result: "); System.out.println("Max:" + max); System.out.println("startPos:" + startPos + ",endPos:" + (endPos - 1)); }}Running results:
For more information about Java algorithms, readers who are interested in this site can view the topics: "Java Data Structure and Algorithm Tutorial", "Summary of Java Operation DOM Node Tips", "Summary of Java File and Directory Operation Tips" and "Summary of Java Cache Operation Tips"
I hope this article will be helpful to everyone's Java programming.