vlambda博客
学习文章列表

Methods and algorithm design

First of all, if all numbers are positive, the result would be the whole array since the summation can only go up or keep the same instead of going down. The result can be given in O(1) time immediately. All analysis below assume there are both positive and negative numbers in the array.

Brute force method is to enumerate all possible sub-arrays where start from each element and finally end at the last element with different middle length. Therefore, a start index and an end index needed to be maintained. Try each case by setting the start index the same and changing the end index till the end of array to see all sub-arra start from the start index, and try every index as the start index. Find the maximum summation by maintain a "max" variable and keep comparing the "max" and summation of different sub-arrays to always select the maximum value. There are n² cases where n is the element of array.

//naiveclass Solution { public int maxSubArray(int[] nums) { if(nums.length == 0){ return 0; } int max = nums[0]; int temp; for(int i = 0; i<nums.length; i++){ temp = nums[i]; max = Math.max(temp,max); for(int j = i+1; j<nums.length; j++){ temp += nums[j]; max = Math.max(temp,max); } } return max; }}

Can we do it better? Good new is yes by using a more mathematical method: dynamic programming. It can always give a better solution  if the problem can be solved using dynamic programming. This problem can be because it satisfies both overlapping subproblems and optimal substructure. Once the recursive formulation is found, the problem is solved.

Why there are overlapping subproblems? When computing start index @ 1st and end index @ last element, all elements in the middle of the array have been computed once. When computing start index @ 2nd and end index @ last element, the middle elements after index of 2nd until the last element are computed one more time and so on. Therefore, some of the problems when enumerating all cases is the same which is overlapped problem. We computed them (e.g. summation of index 4th and 5th) multiple times!

Why there is an optimal substructure? Suppose index 3rd to index 7th is the maximum summation interval. All substructures for example from index @ 1st to index @ last element, from index @ 2nd to index @ 9th etc would give the same answer which is index 3rd to 7th because this interval is the maximum summation interval. Therefore, an optimal solution is also an optimal solution of all other substructures.

How to find recursive formulation? If there is a negative number, the summation would be decreased to a smaller postive number or to a negative number. There is still possibility that the negative is in an optimal solution if the summation is still positive because the positive number and negative in this subarray are not cancelled and positive number is larger than negative number. The overall result of this subarray is still positive. However, if the summation is negative, this subarray can be discarded because it does not help for the latter elements since the start summation is negative if we add the next element to this subarray. Therefore, the recursive formulation is:

Another same size array 'c' need to be created to store the local optimal. The local optimal can be computed using recursive formulation  given above by checking whether the previous local optimal is bigger, or this element is bigger. If the previous summation after adding this element 'i' is bigger, we could put the bigger summation of all of these element in c[i]. Otherwise, the previous summation could only lower the value of nums[i], we discard previous elements, and set the local optimal to 'i' itself. A maximum variable needs to be created in order to record the maximum value in c[i] while we building array 'c' or go through array 'c' after finishing the build of array 'c'. Then we could get the global optimal solution.

//dpclass Solution { public int maxSubArray(int[] nums) { if(nums.length == 0){ return 0; } int[] dp = new int[nums.length]; int max = nums[0]; dp[0] = nums[0];  for(int i = 1; i < nums.length; i++){ if(dp[i-1] > 0){ dp[i] = nums[i] + dp[i-1]; } else{ dp[i] = nums[i]; } max = Math.max(max,dp[i]); } return max; }}

Divide and conquer algorithm can also be applied on this problem. The performance is not that good compared with the DP solution. But it is a good teaching and learning material for divide and conquer. The idea of divide and conquer is to convert a bigger problem to a smaller subproblem. And eventually merge the result of each subproblem to get the optimal solution. We could divide this problem into left and right part until there is only one element in each subproblem. Then do a single O(1) time comparison and merge the result together. There are three possibilities for divide and conquer algorithm. One is the solution is always in the left part, one is always in right part, another one is cross the left part and right part. The third one is the tricky part. Since the performance of this method is worse than DP, no presentation here, instead, the detailed code is given for reference only.

//divide and conquerpublic class Solution { public int maxSubArray(int[] nums) { /* Divide-and-conquer method. The maximum summation of subarray can only exists under following conditions: 1. the maximum summation of subarray exists in left half. 2. the maximum summation of subarray exists in right half. 3. the maximum summation of subarray exists crossing the midpoints to left and right.  1 and 2 can be reached by using recursive calls to left half and right half of the subarraies.  Condition 3 can be found starting from the middle point to the left,    then starting from the middle point to the right. Then adds up these two parts and return.      T(n) = 2*T(n/2) + O(n) this program runs in O(nlogn) time    */ int maxsum = subArray(nums, 0, nums.length-1); return maxsum;} private int subArray(int[] A, int left, int right){ if (left == right){ //base case return A[left]; } int mid = left + (right-left)/2; int leftsum = subArray(A, left, mid); //left part of the subarray sum, condition 1 int rightsum = subArray(A, mid+1, right); //right part of the subarray sum, condition 2 int middlesum = midSubArray(A, left, mid, right); //cross part of the subarray sum, condition 3 // System.out.println(leftsum); // System.out.println(rightsum);    // System.out.println(middlesum);     //following if condition will return middlesum if lost the "=" under the conditon of leftsum = rightsum, which may be problematic if leftsum = rightsum < middlesum. //for example: [-1, -1, -2, -2] if (leftsum >= rightsum && leftsum >= middlesum){ return leftsum; } if (rightsum >= leftsum && rightsum >= middlesum){ return rightsum; } return middlesum;} private int midSubArray(int[] A, int left, int mid, int right){ int leftsum = Integer.MIN_VALUE; int rightsum = Integer.MIN_VALUE; int sum = 0; for (int i = mid; i >= left; i--){ sum += A[i]; if (leftsum < sum){ leftsum = sum; }    } sum = 0; for (int j = mid + 1; j <= right; j++){ sum += A[j]; if (rightsum < sum){ rightsum = sum; }    }     return leftsum + rightsum;}}