求连续子数组的最大和

这题最操蛋的是，输入竟然是一个字符串，但是又没有说明。

import java.util.*;
/*
数组的子数组最大和问题
从前向后累加，每累加一个判断是否是新的最大值
若累加值<=0，说明左边的数组对右边的数组继续累加没有意义，则重新开始累加
比如1，2，-4，5，6这样一个数组
累加到1时，最大和为1
累加到2时，最大和为3
累加到-4时，结果为-1，最大和仍为3，但由于左边三个数之和为-1，右边的子序列包括这一段不能使和更大，
因此从5开始重新累加
最终最大子序列和为11
*/
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String inputStr = scanner.next();
        String[] inputStrs = inputStr.split(",");
        long sum = 0;
        long max = 0;
        for (String str : inputStrs) {
            long num = Integer.parseInt(str);
            sum += num;
            max = max > sum ? max : sum;
            sum = sum < 0 ? 0 : sum;
        }
        System.out.println(max);
    }
}

a=input().split(',')
maxm=num=0
for j in a:
    num=num+int(j) if num+int(j)>0 else 0#如果当前和非负则保留，为负则舍弃
    maxm=max(maxm,num)
print(maxm)

```java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Solution17_求连续子数组的最大和 {

public static void main(String[] args) throws IOException {
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    String[] line1 = bf.readLine().split(",");
    int[] nums = new int[line1.length];
    for (int i = 0; i < line1.length; i++) {
        nums[i] = Integer.parseInt(line1[i]);
    }
    int max = Integer.MIN_VALUE, cur_sum = 0;
    for (int i = 0; i < nums.length; i++) {
        //如果当前累计的和比0还小，直接抛弃，一个数加上一个负数肯定比原来小，直接取当前数
        if (cur_sum <= 0) {
            cur_sum = nums[i];
        } else {
            cur_sum += nums[i];
        }
        //更新最大值
        if (max < cur_sum) {
            max = cur_sum;
        }
    }
    System.out.println(max > 0 ? max : 0);
}

}```

#include <bits/stdc++.h>
using namespace std;

int main(){
    int x;
    vector<int> a;
    while(cin>>x){
        a.push_back(x);
        char c = getchar();
        if(c=='\n')
            break;
    }
    int Max=0, s = 0;
    for(int i=0;i<a.size();i++){
        if(s+a[i]<0)
            s = 0;
        else{
            s += a[i];
            Max = max(Max,s);
        }
    }
    cout<<Max<<endl;
    return 0;
}

动态规划求解：

int max（int n，int *a）

｛

int sum=0；

int b=0；

for（int i=1；i《n；i++）

｛

if（b》0）

b+=a【i】；

else

b=0；

if（sum《b）

sum=b；

｝

if（sum》0）

printf（sum）；

else

printf（0）；

｝

#include<bits/stdc++.h>
using namespace std;
int main() {
    int ans = 0;
    int sum = 0;
    int tempValue = 0;
    while (~scanf("%d%c",&tempValue))
    {
        sum += tempValue;
        if (sum < 0)
            sum = 0;
        if (sum > ans)
            ans = sum;
    }
    cout << ans<< endl;
}

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,sum,maxsum=0;
    vector<int> arr;
    arr.reserve(10000);
    while(scanf("%d,",&n)>0)
        arr.push_back(n);
    sum=arr[0];
    maxsum=max(sum,maxsum);
    for(int i=1;i<arr.size();i++)
        if(sum+arr[i]<0)
            sum=0;
        else{
            sum+=arr[i];
            maxsum=max(maxsum,sum);
        }
    cout<<maxsum;
    return 0;
}

"""
最大子段和问题
ans[i]记录以i结尾的最大子段和
"""
import sys

if __name__ == "__main__":
    # sys.stdin = open("input.txt", "r")
    a = list(map(int, input().strip().split(',')))
    ans = [0]
    temp = 0
    for c in a:
        temp = max(0, temp) + c
        ans.append(temp)
    print(max(ans))

	

while ((line = await readline())) {
        let tokens = line.split(",");

        let arr = tokens.map((item) => +item);
        let len = arr.length;
        let bigNum = 0;
        let i = 0;

        while (i < len) {
            let nowNum = 0;
            for (let j = i; j < len; j++) {
                nowNum += arr[j];
                if (nowNum > bigNum) {
                    bigNum = nowNum;
                }
            }
            i++;
        }
        console.log(bigNum >= 0 ? bigNum : 0)
    }

package main

import (
    "fmt"
)

func main() {
    var x,sum,max int
    for{
        _,ok:=fmt.Scan(&x)
        if ok!=nil{
            break
        }
        if sum+x<x{
            sum=x
        }else{
            sum+=x
        }
        if sum>max{
            max=sum
        }
    }
    fmt.Print(max)
}

const arr =  readline().split(',')
let res = 0
let cur = 0
arr.forEach(str => {
    let num = Number(str)
    if (cur + num < 0) {
        cur = 0
    } else {
        cur += num
        res = Math.max(res, cur)
    }
})
print(res)

import java.util.*;

public class Main {
    
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        String[] ss = s.split(",");
        int[] nums = new int[ss.length];
        
        for(int i = 0; i < ss.length; i++)
            nums[i] = Integer.parseInt(ss[i]);
        
        int ans = maxSum(nums);
        System.out.println(ans);
    }
    
    private static int maxSum(int[] nums){
        
        int max = 0;
        int cur = 0;
        
        for(int num : nums){
            
            cur = Math.max(cur,0);
            cur += num;
            max = Math.max(cur,max);
        }
        return max > 0 ? max : 0;
    }
}

import sys

in_num = sys.stdin.readline().strip().split(',')
num = [int(i) for i in in_num]

res = []
for length in range(len(num), 0, -1):
    for i in range(len(num) - length + 1):
        now_num = num[i:i + length]
        res.append(sum(now_num))
final_res = max(res)
if final_res < 0:
    print(0)
else:
    print(final_res)

#include<iostream>
(720)#include<vector>

using namespace std;

int main(void){
    string s;
    cin>>s;
    vector<long> v;
    int k;
    while ((k = s.find(',')) != s.npos){
        string temp = s.substr(0, k);
        v.push_back(stol(temp));
        s = s.substr(k+1);
    }
    v.push_back(stol(s));
    vector<long> dp(v.size());
    long MaxAns = 0;
    for (int i = 0; i < v.size(); i++){
        if (i == 0)
            dp[i] = v[i];
        else{
            if (dp[i-1] >= 0)
                dp[i] = dp[i-1] + v[i];
            else
                dp[i] = v[i];
        }
        MaxAns = max(dp[i], MaxAns);
    }
    cout<<MaxAns<<endl;
    return 0;
}