Method to find the sum of the largest subarray (2 options)

Problem description: an array with n elements, which can be positive or negative, is the sum of the largest subarray.

Method 1: brute force method

Idea: the easiest and easiest way to think about it is to find all the subarrays, and then find the sum of all the subarrays, and take the maximum value in the sum of all the subarrays.

/**
  *  methods 1 (brute force method) : loop twice to find the sum of the largest subarray 
  */
 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

First, according to the relationship between a[n-1], the last element of the array, and the largest subarray, there are three cases as follows:

1) the largest subarray contains a[n-1], ending in a[n-1].

2) a[n-1] alone constitutes the largest subarray.

3) the largest subarray does not contain a[n-1], so finding the largest subarray of a[1,..., n-1] can be converted to finding the largest subarray of a[1,..., n-2].

The following conclusion can be drawn from the above analysis: it is assumed that (a[0],... a[i-1]), the largest one-segment array, is All[i-1], and it is also calculated that (a[0]... a[i-1]) contains the largest one-segment array of a[i-1] and is End[i-1],

Then the following relationship can be obtained: All[i-1]=max{a[i-1],End[i-1],All[i-1]}. Using this formula and the idea of dynamic programming to solve the problem. (the starting and ending positions are also resolved in the code.)

/**
  *  methods 2 : an optimized dynamic programming method 
  * nEnd I'm just adding up the array a[i] And then with a[i] Compare the "get" and save the larger one. Because if the previous number is added to a[i]
  *  Has not yet been a[i] If it is large, then the preceding number contributes nothing to the maximum subarray sum. severe 
  * nAll Is the record 1 Let's do the new one nEnd And oneself before who is bigger 
  */
 public static int max(int m,int n){
  return m>n?m:n;
 }
 public static int maxSubArray2(int[] a){
  int nAll=a[0];// There are n The sum of the largest subarray of an array of Numbers 
  int nEnd=a[0];// There are n An array of Numbers contains the end 1 The maximum sum of a subarray of elements 
  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 beginning of the largest subarray begin End, end And 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;
 }