Problem description: An array with n elements, these n elements can be positive or negative. Find the sum of the largest subarray.
Method 1: Brute force method
Idea: The easiest and easiest way to think of is to find all subarrays, then find the sum of all subarrays, and get the maximum value in the sum of all subarrays.
/** * Method 1 (brute force method): Find the sum of the maximum subarrays in two loops*/ public static int maxSubArray1(int[] a){ int i,j; int ThisSum=0; int MaxSum=0; for (i = 0; i < a.length; i++) { ThisSum=a[i]; for(j=i+1;j<a.length;j++){ ThisSum+=a[j]; if(ThisSum>MaxSum){ MaxSum=ThisSum; } } return MaxSum; }Method 2: Optimized Dynamic Programming
Idea: First, according to the relationship between the last element a[n-1] of the array and the largest subarray, it can be divided into the following three situations:
1) The maximum subarray contains a[n-1], that is, ending with a[n-1].
2) a[n-1] alone forms the largest subarray.
3) The maximum subarray does not contain a[n-1], so finding the maximum subarray of a[1,...,n-1] can be converted to finding the maximum subarray of a[1,...,n-2].
Through the above analysis, we can draw the following conclusion: Assuming that the sum of the largest array of (a[0],...a[i-1]) has been calculated as All[i-1], and the sum of the largest array of a[i-1] in (a[0],...a[i-1]) is also calculated as End[i-1].
Then the following relationship can be obtained: All[i-1]=max{a[i-1],End[i-1],All[i-1]}. Use this formula and the idea of dynamic programming to solve problems. (The code also solves the problem of starting position and ending position)
/** * Method 2: Optimized dynamic programming method* nEnd is obtained by adding arrays to a[i] in sequence, and then comparing them with a[i]", and saved the larger one. Because if the previous number is added to a[i] * is not as large as a[i] itself, then the previous number will have no contribution to the largest subarray. * nAll is to record which one has the new nEnd before and which one has the largest before*/ public static int max(int m,int n){ return m>n?m:n; } public static int maxSubArray2(int[] a){ int nAll=a[0];//The sum of the maximum subarrays of n numeric arrays int nEnd=a[0];//The sum of the subarrays of n numeric arrays contain the last element for (int i = 1; i < a.length; i++) { nEnd=max(nEnd+a[i],a[i]); nAll=max(nEnd, nAll); } return nAll; } private static int begin=0; private static int end=0; /** * Find the start and end of the largest subarray of subarray, as well as the entire subarray*/ public static int maxSubArray3(int[] a){ int maxSum=Integer.MIN_VALUE; int nSum=0; int nStart=0; for (int i = 0; i < a.length; i++) { if(nSum<0){ nSum=a[i]; nStart=i; } else{ nSum+=a[i]; } if(nSum>maxSum){ maxSum=nSum; begin=nStart; end=i; } } return maxSum; }The above is all the content of this article. I hope that the content of this article will be of some help to everyone’s study or work. I also hope to support Wulin.com more!