Shulou(Shulou.com)05/31 Report--

This article mainly introduces "how to find the sum of the largest continuous subsequence in an integer array by Java". In daily operation, I believe that many people have doubts about how to find the sum of the largest continuous subsequence in an integer array by Java. The editor consulted all kinds of data and sorted out a simple and useful method of operation. I hope it will be helpful for everyone to answer the question of "how to find the sum of the largest continuous subsequence in an integer array". Next, please follow the editor to study!

/ * *

Dynamic programming (Dynamic Programming):

The main results are as follows: 1) the problem to be solved is divided into several sub-problems (that is, the process of solving the problem is divided into several stages), and the solution of the former sub-problem provides useful information for the solution of the latter sub-problem.

2) when solving any sub-problem, list the possible local solutions, retain the local solutions that are likely to be optimal through decision making, and discard other local solutions.

3) solve each sub-problem in turn, and the solution of the last sub-problem is the solution of the initial problem.

Problem: find the sum of the largest continuous subsequence in an integer array, which contains both positive and negative integers.

For example: array int [] array = {1,-3, 7, 8,-4, 10,-19, 11}; the largest contiguous subsequence in the array is: 7, 8,-4, 10, their sum is 21

, /

Public class DP {/ * brute force solution * * time complexity: O (N ^ 2) * / public static int maxSubSumByEnum (int [] array) {int maxSum = 0; int begin = 0; int end = 0; / * 1) the maximum value of a continuous subsequence starting with the I element can be found at the end of the I-th cycle. * 2) I represents the beginning of the sequence and j represents the end of the sequence. * 3) move the end point backwards in each cycle: one bit at a time and calculate the sum of the current sequence. At the end of the cycle, we can get the subsequence and the maximum value of the cycle. * / for (int I = 0; I

< array.length; i++) { // int tempSum = 0; for (int j = i; j < array.length; j++) { tempSum += array[j]; if (tempSum >

MaxSum) {maxSum = tempSum; begin = I; end = j;}} System.out.println ("begin:" + begin + "end:" + end); return maxSum } / * dynamic programming * * time complexity: O (N) * key points: * 1) if the sum of continuous subsequences in the current stage is less than 0, then proceed to the next stage, and determine the starting point of the next stage and initialize the sum of the next stage to 0. * 2) the starting point and end point of the largest continuous subsequence in the array will be updated only when the sum of the current stage is greater than the maximum sum of history. * / public static int maxSubSumByDP (int [] array) {int maxSum = 0; / / in the array, the sum of the largest continuous subsequence int begin = 0; / / in the array, the starting point of the largest continuous subsequence int end = 0; / / in the array, the end point of the largest continuous subsequence int tempSum = 0; / / in the current stage, the sum of the continuous subsequence int tempBegin = 0 / / in the current phase, the starting point of the continuous subsequence for (int I = 0; I)

< array.length; i++) { tempSum += array[i]; if (tempSum < 0) { // 若当前阶段中连续子序列的和小于0，则进入下一阶段 tempSum = 0; // 下一阶段的和进行归零处理 tempBegin = i + 1; // 下一阶段的起点 } else if (tempSum >

MaxSum) {/ / if the sum of the current phase is greater than the historical maximum sum, update the start and end of the largest continuous subsequence in the array. MaxSum = tempSum; begin = tempBegin; end = I;} System.out.println ("begin:" + begin + "end:" + end); return maxSum;} public static void main (String [] args) {int [] array = {1,-3,7,8,-4,10,-19,11}; int dpMax = maxSubSumByDP (array); System.out.println (dpMax) Int enumMax = maxSubSumByEnum (array); System.out.println (enumMax);}

}

At this point, the study of "how to find the sum of the largest continuous subsequence in an integer array by Java" is over. I hope to be able to solve your doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.