子数组的最大累加和问题

//第一种：累加和小于0，则归零继续往后面遍历   
public int maxsumofSubarray (int[] arr) {
   
        if(arr==null||arr.length==0) return -1;
        int n=arr.length,max=0,sum=0;
        for(int i=0;i<n;i++){
            sum=sum+arr[i];
            if(sum>max)  max=sum;
            if(sum<0) sum=0;
            
        }
        return max;
    }
}
//第二种，dp 存储到第i个元素时的最大和
    public int maxsumofSubarray (int[] arr) {
       int n=arr.length,dp=0,max=0;
        for(int i=0;i<n;i++){
            dp=Math.max(arr[i],dp+arr[i]);
            max=Math.max(max,dp);
        }
        return max;
    }

class Solution:
    def maxsumofSubarray(self , arr ):
        ans = 0
        cum = 0
        for i in arr:
            cum += i
            if cum < 0:
                cum = 0
            elif cum > ans:
                ans = cum
        return ans

  public int maxsumofSubarray (int[] arr) {
        //1.dp状态设置： dp[i]就是以nums[i]为结尾的的连续子数组的最大和
        int[] dp = new int[arr.length];
        //2.初态设置：dp[0]必须包含nums[0] 所以：
        dp[0] = arr[0];
        int res = dp[0];
        //3.转移方程：
        //因为nums[i]无论如何都要包括 那么可以选择的余地就是dp[i-1]了
        //dp[i-1]<0 那么不如只选nums[i]了 dp[i-1]>0 那就nums[i]带上dp[i-1]
        for (int i = 1; i < arr.length; i++) {
           dp[i] =  dp[i-1]>0?dp[i-1]+arr[i]:arr[i];
           //由于无论如何都要包括nums[i] 那么如果最后的nums[len-1]<0
            //那么此时dp[len-1]肯定不是最大连续和 需要max筛选
            res = Math.max(res,dp[i]);
        }
        return res;
    }

正确的代码不可以通过,错误代码可以通过.....呵呵

js榜都是错的，怎么通过的都？

思路：

1. 设置一个变量max存储全局最大值，一个变量cur存储当前的和；

2. 然后开始遍历数组:

   1. 将cur加上当前的值获得新cur；
   2. 如果新cur小于0，则重置cur为0，并继续下一循环；
   3. 如果新cur大于max，则更新max；

function maxsumofSubarray( arr ) {
    let max = 0, cur = 0;
    for (const num of arr) {
        cur += num;
        if (cur < 0) cur = 0;
        else if (max < cur) max = cur;
    }
    return max;
}

int maxsumofSubarray(vector<int>& arr) {
        // write code here
        int maxresult = 0;
        int curresult = 0;
        for(int i = 0;i<arr.size();i++)
        {
            curresult += arr[i];
            if(curresult < 0)
            {
                curresult = 0;
            }
            if(curresult > maxresult)
            {
                maxresult = curresult;
            }
        }
        return maxresult;
    }

function maxsumofSubarray( arr ) {
    // write code here
  let max = Number.MIN_VALUE
  let pre = 0
  for(let i = 0; i < arr.length; i++) {
    pre = Math.max(arr[i], pre + arr[i])
    max = Math.max(max, pre)
  }
  return max
}
module.exports = {
    maxsumofSubarray : maxsumofSubarray
};

public class Solution {
    public int maxsumofSubarray (int[] arr) {
        int max = 0;
        int cumsum = 0;
        for(int i = 0; i < arr.length; i++){
            if(cumsum >= 0){
                cumsum += arr[i];
            }
            else{
                cumsum = arr[i];
            }
            max = Math.max(max, cumsum);
        }
        return max;
    }
}

#
# max sum of the subarray
# @param arr int整型一维数组 the array
# @return int整型
class Solution:
    def maxsumofSubarray(self , arr ):
        # write code here
        num_c = 0
        num_r = arr[0]
        for i in range(len(arr)):
            num_c += arr[i]
            if i > 0:
                num_r = max(arr[i],num_c,num_r)
            if num_c < 0:
                num_c = 0
        return num_r

        int maxsumofSubarray(vector<int>& arr) 
    {
        int temp = 0; int result = arr[0];
        for(int i=0;i<arr.size();i++)
        {
            temp = max(temp+arr[i],arr[i]);
            result = max(result,temp);
        }
        return result;
        // write code here
    }
遍历数组，看看是累加到当前元素的和大 还是当前元素大，并更新temp的值

有写go的小伙伴吗？
思路：
.子数组必然以正数开始，其实就是分析一个子结构，类似：[+a1, +a2, -a3, -a4, +a5]
.问题本质就是，在两个正子数组之间的负子数组是否应该被计算在内的问题
.如果负子数组元素和的绝对值分别小于前后正子数组的元素和，则应该被计算在内，否则前后正子数组的元素和的较大者为可能的结果。

package main

func maxsumofSubarray( arr []int ) int {
    res := 0
    tmp := 0
    for i := 0; i < len(arr); i++ {
        res += arr[i]
        if arr[i] > 0 && res <= 0 {
            res = arr[i]
        }
        if arr[i] < 0 && res > tmp{
            tmp = res
        }
    }
    return res
}

class Solution {
public:
    /**
     * max sum of the subarray
     * @param arr int整型vector the array
     * @return int整型
     */
    int maxsumofSubarray(vector<int>& arr) {
        int a = arr.size();
        int dp[a];
        dp[0] = arr[0];
        for(int i = 1; i < arr.size(); i++){
            if(dp[i-1] >=0){
                dp[i] = dp[i-1]+arr[i];
            }
            else{
                dp[i] = arr[i];
            }
        }
        return dp[a-1];
    }
};

class Solution {
public:
    /**
     * max sum of the subarray
     * @param arr int整型vector the array
     * @return int整型
     */
    int maxsumofSubarray(vector<int>& arr) {
        int a = arr.size();
        int dp[a];
        dp[0] = arr[0];
        int _max = dp[0];
        for(int i = 1; i < arr.size(); i++){
            if(dp[i-1] >=0){
                dp[i] = dp[i-1]+arr[i];
            }
            else{
                dp[i] = arr[i];
            }
            _max = max(_max, dp[i]);
        }
        return _max;
    }
};

import java.util.*;


public class Solution {
    /**
     * 【逆向思维】要找出一个子串，使得和最大
     * 相对来说是去掉了左边和右边的数据，剩下一个子串
     * 所以用左右两个指针，依次找从左到右，从右到左的连续最小和index
     * 那么这两者之间的子串就是目标子串
     * 同时，需要考虑指针碰撞，也就是所有值为负数，那么找出其中的最大的单值
     */
    public int maxsumofSubarray (int[] arr) {
        if(arr.length <=1){
            return arr[0];
        }
        
        int leftMin = arr[0];
        int leftIndex = 0;
        int tmp = arr[0];
        // 保存最大值，用于指针碰撞后返回
        int max=arr[0];
        for(int i = 1; i < arr.length; i ++){
            tmp += arr[i];
            if(tmp < leftMin){
                leftMin = tmp;
                leftIndex = i;
            }
            
            if(arr[i]>max){
                max = arr[i];
            }
        }

        int rightMin = arr[arr.length-1];
        int rightIndex = arr.length-1;
        tmp = arr[arr.length-1];
        for(int j = arr.length-2; j >= 0; j --){
            tmp += arr[j];
            if(tmp < rightMin){
                rightMin = tmp;
                rightIndex = j;
            }
        }

        // 指针碰撞了，返回最大值
        if(leftIndex>=rightIndex){
            return max;
        }else{
            // 找到左右指针，同时要判断左右指针的值是否大于0
            tmp = 0;
            for(int k = leftIndex+1; k <= rightIndex-1; k ++){
                tmp += arr[k];
            }
            
            if(arr[leftIndex]>0){
                tmp += arr[leftIndex];
            }
            
            if(arr[rightIndex]>0){
                tmp += arr[rightIndex];
            }

            return tmp;
        }
    }
}

动态规划

public class Solution {
    /**
     * max sum of the subarray
     * @param arr int整型一维数组 the array
     * @return int整型
     */
     //动态规划 时间O(n)，空间O(1)
    //转移方程
    /*dp[i] 代表以元素 nums[i] 为结尾的连续子数组最大和
      当dp[i-1] >0  时：执行 dp[i] = dp[i-1] + nums[i]
      当dp[i-1] <=0 时：执行 dp[i] = nums[i];
     */
    public int maxsumofSubarray (int[] arr){
        // write code here
        if (arr.length == 0) return 0;
        int len = arr.length;
        int cur,pre = arr[0],res = arr[0];
        for(int i = 1;i < len;++i){
            cur = arr[i];
            cur = cur + Math.max(pre,0);
            pre = cur;
            res = Math.max(res,cur);
            //也可以直接在arr[] 上做修改
//          arr[i] = arr[i] + Math.max(arr[i-1],0);
//          res = Math.max(arr[i],res);
        } 
        return res;
    }
}