question
//Given an integer array nums, // please find a continuous sub-array with "maximum sum" (the sub-array contains at least one element), // return its maximum sum.
//A subarray is a "continuous part" of the array
analyze
// This is a typical use of "dynamic programming"
(continuous, as long as the result) solves the problem,
// We need to master the skills of dynamic programming problem design state (no aftereffect),
// and need to know how to derive the state transition equation,
// Finally, optimize the space.
Convert to several subproblems
Continuous: You can find the maximum sum of "all" continuous sub-arrays of a certain number of input arrays (ending with **) (as long as this result).
If the result of subproblem number i is negative or 0,
Then the sub-problem numbered i + 1 can "discard" the result of the sub-problem numbered i (because the requirement is the maximum sum)
the code
main function
package DataStructure_start;
public class DS20230109 {
public static void main(String[] args) {
int[] nums = {-1,9,-2,3,5,6};
System.out.println(maxSubArray(nums));
System.out.println(maxSubArray1(nums));
System.out.println(maxSubArray2(nums));
System.out.println(maxSubArray3(nums));
}
}Method 1: Dynamic Programming
Reference 1: (subarray)
Time complexity: O(n), where N is the length of the input array
public static int maxSubArray(int[] nums) {
int len = nums.length;
// dp[i] means: the maximum sum of consecutive subarrays ending in nums[i]
int[] dp = new int[len];
dp[0] = nums[0];
// If the result of subproblem number i is negative or 0,
// Then the sub-problem numbered i + 1 can "discard" the result of the sub-problem numbered i (because the requirement is the maximum sum)
// That is: if the result of the subproblem of i is positive, keep
for (int i = 1; i < len; i++) {
// If the previous number is positive
if (dp[i - 1] > 0) {
// then add the next number
// ? But only adjacent two numbers ×
// dp[i] means: the maximum sum of consecutive subarrays ending in nums[i]
// Pay attention to the difference between dp[] (a continuous array) and num[] (a number)
dp[i] = dp[i - 1] + nums[i];
} else {
dp[i] = nums[i];
}
}
// You can also find the maximum value of res while traversing above. Here we write it separately for semantic clarity. You can choose by yourself
int res = dp[0];
for (int i = 1; i < len; i++) {
res = Math.max(res, dp[i]);//Call the function Math: max function: determine who is the maximum value (ternary expression)
}
return res;//returns the maximum sum
}Replenish:
ternary expression
public static int max(int a, int b) {
return (a >= b) ? a : b;
}
The time complexity is sorted from small to large:
(Analyze the time complexity from the inside out; take the maximum time complexity)
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
Reference 2: After optimization
Time complexity: O(n), where N is the length of the input array
public static int maxSubArray1(int[] nums) {
int pre = 0;//previous number
int res = nums[0];//Maximum sum
// Only applicable to arrays, cyclic accumulation (optimization point ★)
for (int num : nums) {
pre = Math.max(pre + num, num);
res = Math.max(res, pre);
}
return res;
}With aftereffect:
If the results of the sub-problems solved in the previous stage contain some uncertain information, which makes the sub-problems solved in the later stage unobtainable or difficult to obtain, this is called "consequence effect".
The solution to "consequences" is to fix the places that need to be classified and discussed, and record more results. At the code level, it manifests as:
The state array increases the dimension;
Define the state more carefully and accurately: the state definition only resolves one of the subtrees whose path comes from the left and right subtrees.
Need to often think about why you need to define the state in this way.
Dynamic programming is to traverse the array first, the current maximum continuous subsequence sum is sum, and the result is ans
If sum > 0, it means that sum has a positive effect on the result, then sum is reserved and added to the current traversal number
If sum <= 0, it means that sum has no gain effect on the result and needs to be discarded, then sum is directly updated to the current traversal number
Each time the size of sum and ans is compared, the maximum value is set as ans, and the result is returned after the traversal
Time complexity: O(n)
public static int maxSubArray3(int[] nums) {
int ans = nums[0];
int sum = 0;
// Similar to method 1 here, refer to the optimization part in 1, that is, the for loop array
for(int num: nums) {
// A positive number
if(sum > 0) {
// accumulative sum
sum += num;
// Negative numbers, stay the same
} else {
sum = num;
}
// Ternary expression: comparison to take the maximum value
ans = Math.max(ans, sum);
}
return ans;
}Method 2: Divide and conquer (discussion by category, divided into three parts)
Complexity analysis:
Time complexity: O(NlogN), where the depth of recursion is logarithmic, and each layer needs to traverse the array (or half or quarter of the array);
Space complexity: O(logN), requires a constant number of variables to select the maximum value, and the space to be used depends on the depth of the recursive stack.
The maximum sum of consecutive subsequences is mainly obtained by the maximum sum of elements in these three subintervals:
part 1: subinterval [left, mid];
Part 2: subinterval [mid + 1, right];
Part 3: the subinterval containing the subinterval [mid , mid + 1],
That is, nums[mid] and nums[mid + 1] must be selected (because of cross-region. Spread from the middle to both sides, and spread to the end to select the maximum value).
Find the maximum of these three parts.
public static int maxSubArray2(int[] nums) {
int len = nums.length;
if (len == 0) {
return 0;
}
return maxSubArraySum(nums, 0, len - 1);
}
private static int maxCrossingSum(int[] nums, int left, int mid, int right) {
// Must contain the element nums[mid]
int sum = 0;
int leftSum = Integer.MIN_VALUE;
// The left half contains nums[mid] elements, up to where
// Go to the extreme boundary and see what the maximum value is
// Computes the largest subarray sum ending in mid
for (int i = mid; i >= left; i--) {
sum += nums[i];
if (sum > leftSum) {
leftSum = sum;
}
}
sum = 0;
int rightSum = Integer.MIN_VALUE;
// The right half does not contain nums[mid] elements, where can it go at most
// Computes the sum of the largest subarray starting at mid+1
for (int i = mid + 1; i <= right; i++) {
sum += nums[i];
if (sum > rightSum) {
rightSum = sum;
}
}
return leftSum + rightSum;
}
private static int maxSubArraySum(int[] nums, int left, int right) {
if (left == right) {
return nums[left];
}
int mid = left + (right - left) / 2;
return max3(maxSubArraySum(nums, left, mid),
maxSubArraySum(nums, mid + 1, right),
maxCrossingSum(nums, left, mid, right));
}
private static int max3(int num1, int num2, int num3) {
return Math.max(num1, Math.max(num2, num3));
}refer to
Author: liweiwei1419
Source: LeetCode
Author: guanpengchn
Source: LeetCode