连续子数组最大和

Erlang人生动态规划
解题思路

如果到目前为止你的过去是负担，那就放下吧，每天都是新的开始~

如果到目前为止你的过去是正担，那就带上吧，试试找到自己人生的最大子序和吧~（即自己相对提升最大的一段时间，我希望是现在也是未来）

代码

-spec max_sub_array(Nums :: [integer()]) -> integer().
max_sub_array(Nums = [NumH | NumsT]) ->
    do_max_sub_array(NumsT, #{nums => [NumH]}).

do_max_sub_array([Num | T], Args = #{nums := Nums = [PreSum | _]}) ->
    Sum = case PreSum >= 0 of
        true ->
            Num + PreSum;
        _ ->
            Num
    end,
    do_max_sub_array(T, Args#{nums := [Sum | Nums]});
do_max_sub_array([], _Args = #{nums := Nums}) ->
    lists:max(Nums).

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int arr[n], dp[n];
    for (int i = 0; i < n; ++i) cin >> arr[i];
    // 时间复杂度O(N)，空间复杂度O(1)
    int dp0 = arr[0], dp1, res = arr[0];
    for (int i = 1; i < n; ++i) {
        // i位置处最大子数组和，一定包含i-1位置的数，这样才能保证连续
        dp1 = max(dp0 + arr[i], arr[i]);
        res = res > dp1 ? res : dp1;
        dp0 = dp1;
    }
    cout << res;
    return 0;
}

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        int [] nums = new int[n];

        for (int i = 0; i < n; i++)
            nums[i] = in.nextInt();

        int res = maxSubArray(nums);

        System.out.println(res);
    }

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

#include <stdio.h>

int main() {
    int n,max;
    scanf("%d",&n);
    int a[n],dp[n];
    for (int i=0; i<n; i++) {
        scanf("%d",&a[i]);
    }
    dp[0]=a[0];
    max=dp[0];
    for (int i=1; i<n; i++) {
        dp[i]=(a[i]>(dp[i-1]+a[i])?a[i]:(dp[i-1]+a[i]));
        max=(dp[i]>max?dp[i]:max);
    }
    
        printf("%d", max);
    
    return 0;
}

#include <iostream>
using namespace std;

int main() {
    int n, res = 0, sum=0;
    cin>>n;
    int x;
    cin>>x; 
    res = x; sum = x;
    while(--n){
        cin>>x;
        if(sum>0){
            res = max(res, sum);
            sum += x;
        }else{
            sum = x;
            res = max(res,sum);
        }
    }
    res = max(res,sum);
    cout<<res;
}
// 64 位输出请用 printf("%lld")

# 解法一
_ = input()
arr = list(map(int, input().split()))

# 初始化s为从第一个元素前开始连续相加的值
s = 0
# 初始化res为第一个元素的值
res = arr[0]

# 遍历数组
for i in arr:
    # 更新s
    s += i
    # 如果更新后的s比res大，则赋值给res
    res = max(s, res)
    # 如果更新后的s小于0，则清空值，从下一个元素开始更新
    s = max(s, 0)

# 最后res即为连续子数组的最大值
print(res)


# 解法二
n = int(input())
arr = list(map(int, input().split()))

dp = [arr[0]]
# 遍历数组
for i in range(1, n):
    # 连加后的值与下一个值作比较，如果连加后比较大，则不取下一个值；如果下一个值比较大，则从下一个值算起
    dp.append(max(arr[i], dp[i - 1] + arr[i]))

print(max(dp))

import sys

nums = []
for line in sys.stdin:
    a = line.split()
    nums = a

m = len(nums)
# 定义dp[i]为选中第i元素的子数据最大值
# 输出为max(dp[1],...,dp[m])
# dp方程：dp[i+1] = max(dp[i] + nums[i], nums[i])
dp = [0] * (m+1)
max_res = -9999
for i in range(m):
    dp[i+1] = max(dp[i] + int(nums[i]), int(nums[i]))
    max_res = max(max_res, dp[i+1])
print(max_res)

#include <iostream>
using namespace std;
const int N = 200010;
int a[N];
int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> a[i];
    int ret = -101, sum = -101;
    for(int i = 0; i < n; i++)
    {
        sum = max(sum + a[i], a[i]);
        ret = max(ret, sum);
    }
    cout << ret << endl;
}

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    let n=await readline();
    let arr=(await readline()).split(" ").map(it=>parseInt(it));
    let max=arr[0],sum=0;
    for(let i=0;i<arr.length;i++){
        sum+=arr[i];
        if(arr[i]>sum) sum=arr[i];
        if(sum>max) max=sum;
    }
    console.log(max);
}()

class Solution:
    def maxstr(self,n,nums):
        dp = [0]*n 
        dp[0] = nums[0]
        for i in range(1,n):
            dp[i] = max(dp[i-1]+nums[i] , nums[i])
        return max(dp)
n = int(input())
nums = list(map(int,input().split()))
a = Solution()
b = a.maxstr(n,nums)
print(b)

while(n = +readline()){
    lines = readline().split(' ')
    lines.forEach(function(ele,index){
        lines[index] = +ele
    })
    var max = lines[0];
    var x = lines[0];
    for(let i=1;i<n;i++){
        x = x+lines[i]>lines[i]?x+lines[i]:lines[i]
        max = max>x?max:x
    }
    console.log(max)
}

# 使用穷举的方法，但是导致超时，部分不能计算正确
n = int(input())
l = list(map(int,input().split()))
l = l+[0,0]
dp=[]
for i in range(n):
    for k in range(i,n):
        dp.append(sum(l[i:k+1]))
print(max(dp))