最大子序和(Maximum suborder sum)-其他

最大子序和(Maximum suborder sum)

1 <= nums.length <= 105
-104 <= nums[i] <= 104

• 设置dp[i]为第i位的暂存值（注意：不是最大值，只是下标滑到第i位时，dp的数值）
• 最大子序和的第一位一定为 正数，
• 如果一个序列全为负数，那么就要求负数的最大值（不要想当然的觉得最大数大于0！然后就随随便便的把dp[i]=0），
• 如果dp[i-1]<=0,那么就要勇敢舍弃前面算的，从当前位重新开始（违反第2条）。
• 如果dp[i-1]>0,当然要加上当前位（贪心），至于加上当前位后是会减少dp[i]或者增加,留给下一个循环去判断。

class Solution {
public int maxSubArray(int[] nums) {

int [] dp = new int [nums.length];
dp[0] = nums[0];

for(int i=1;i<nums.length;i++){
if(dp[i-1]<=0){
dp[i] = nums[i];
}
else{
dp[i] = dp[i-1]+nums[i];
}
}
java.util.Arrays.sort(dp);
return dp[nums.length-1];
}
}

if(dp[i-1]<=0){
dp[i] = nums[i];
}
else{
dp[i] = dp[i-1]+nums[i];
}

dp[i] = nums[i]+Math.max(dp[i-1], 0)

class Solution {
public int maxSubArray(int[] nums) {

int [] dp = new int [nums.length];
dp[0] = nums[0];
int max = dp[0];
for(int i=1;i<nums.length;i++){
dp[i] = nums[i] + Math.max(dp[i-1], 0);
max = Math.max(dp[i], max);
}
return max;
}
}

class Solution {
public int maxSubArray(int[] nums) {
int temp_i = nums[0];
int max = nums[0];
for(int i=1;i<nums.length;i++){
temp_i = nums[i] + Math.max(temp_i, 0);
max = Math.max(temp_i, max);
}
return max;
}
}
————————

Give you an integer array nums. Please find a continuous sub array with the maximum sum (the sub array contains at least one element) and return its maximum sum.

A subarray is a contiguous part of an array.

Example 1:

Example 2:

Example 3:

Tips:

1 <= nums.length <= 105
-104 <= nums[i] <= 104

Advanced: if you have implemented a solution with complexity O (n), try using a more sophisticated divide and conquer method.

Solution 1: dynamic programming + greedy thought

First, understand the following points:

• Set DP [i] as the temporary value of bit I (Note: it is not the maximum value, but the value of DP when the subscript slides to bit I)
• The first bit of the maximum suborder sum must be a positive number,
• If a sequence is all negative numbers, the maximum value of negative numbers is required (do not assume that the maximum number is greater than 0! And then casually set DP [i] = 0),
• If DP [I-1] < = 0, you should bravely abandon the previous calculation and start again from the current bit (in violation of Article 2).
• If DP [I-1] > 0, of course, add the current bit (greedy). Adding the current bit will reduce DP [i] or increase, leaving it to the next cycle to judge.

The code is as follows:

class Solution {
public int maxSubArray(int[] nums) {

int [] dp = new int [nums.length];
dp[0] = nums[0];

for(int i=1;i<nums.length;i++){
if(dp[i-1]<=0){
dp[i] = nums[i];
}
else{
dp[i] = dp[i-1]+nums[i];
}
}
java.util.Arrays.sort(dp);
return dp[nums.length-1];
}
}

The above code does not clearly write the unified equation of dynamic programming, but it is composed of two if in the for loop,

if(dp[i-1]<=0){
dp[i] = nums[i];
}
else{
dp[i] = dp[i-1]+nums[i];
}

It can be inferred that DP formula:

dp[i] = nums[i]+Math.max(dp[i-1], 0)

Therefore, the above code can be simplified as:

class Solution {
public int maxSubArray(int[] nums) {

int [] dp = new int [nums.length];
dp[0] = nums[0];
int max = dp[0];
for(int i=1;i<nums.length;i++){
dp[i] = nums[i] + Math.max(dp[i-1], 0);
max = Math.max(dp[i], max);
}
return max;
}
}

Continue to optimize

class Solution {
public int maxSubArray(int[] nums) {
int temp_i = nums[0];
int max = nums[0];
for(int i=1;i<nums.length;i++){
temp_i = nums[i] + Math.max(temp_i, 0);
max = Math.max(temp_i, max);
}
return max;
}
}