子数组的最大累加和问题

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define max(a,b) ((a) > (b) ? (a) : (b))

int main(void) {
    int n, *arr;
    scanf("%d", &n);
    arr = (int *) malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        scanf("%d", arr + i);
    }
    
    int maxSum = INT_MIN, pre = -1, cur;
    for (int i = 0; i < n; i++) {
        cur = arr[i] + (pre > 0 ? pre : 0);
        maxSum = max(maxSum, cur);
        pre = cur;
    }
    printf("%d\n", maxSum);
    return 0;
}

n=int(input())
number_list=list(map(int,input().split()))
dp=[number_list[i] for i in range(len(number_list))]
for i in range(1,len(number_list)):
    dp[i]=max(dp[i],dp[i-1]+number_list[i])
print(max(dp))

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

int main(){
    int n, x, Max=0;
    cin>>n;
    for(int i=0,s=0;i<n;i++){
        cin>>x;
        s += x;
        if(s<0)
            s = 0;
        else
            Max = max(Max, s);
    }
    cout<<Max<<endl;
    return 0;
}

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        int max = Integer.MIN_VALUE;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += arr[i];
            max = Math.max(sum, max);
            if (sum < 0) {
                sum = 0;
            }
        }

        System.out.println(max);
    }
}

const N = Number(readline());
const arr = readline().split(' ').map(Number);

const dp = [];
// 考虑的角度是寻找以 i 结尾的子数组中，累加和最大的。
// 先用 maxIdx 记下对于每个 i 位置而言， arr[0...i] 的累加和，其中最大的
// 累加和出现的位置。因为对于每个 i 位置而言，从下标 0 开始到 i，已经是以 i
// 结尾的最大子数组长度了，此时 maxIdx 位置，也必将是最终累加和最大的子数组
// 的结尾的位置。因为当你从下标 1, 2, 3, ... i - 1 开始时，子数组长度是在
// 不断缩短的，假如 1 ~ i-1 位置上都是正数，那显然缩短的过程中，以 maxIdx结尾
// 的子数组的累加和会不断减小。假如 1 ~ i-1 上有负数，则在缩短过程中，以 maxIdx
// 结尾的子数组的累加和还有可能增大。
// 为什么最大累加和的子数组一定以 maxIdx 位置结尾？
// 因为在从下标0开始的统计中，maxIdx之后位置结尾的累加和都已经开始变小了，说明
// maxIdx+1 ~ i (i > maxIdx+1)范围上存在负数，以之结尾的子数组累加和是不可能
// 超过maxIdx结尾的子数组累加和的。
let maxIdx = 0;
// 给原始arr前面插入一个0，方便统一从原始arr的第一个元素开始计算累加和。
arr.unshift(0);
for (let i = 1; i < N + 1; i++) {
  arr[i] = arr[i - 1] + arr[i];
  if (arr[i] > arr[maxIdx]) {
    maxIdx = i;
  }
}
// 最终的最大累加和子数组一定以maxIdx结尾，下来只需把i从原始arr的第一个下标开始一直缩短到
// maxIdx - 1位置，寻找这个过程中还有没有可能使累加和变大，
// 因为给arr前面插入了一个0,所以下标从1开始，
let max = arr[maxIdx];
for (let i = 1; i < maxIdx; i++) {
  arr[maxIdx] = arr[maxIdx] - arr[i];
  max = Math.max(max, arr[maxIdx]);
}
console.log(max);

   public static void test(int[] data) {


        int max_sum = 0;// 最大值
        int count = 0;// 累加和初始化
        for (int i = 0; i < data.length; i++) {
            if (data[i] + count > 0) {
                count += data[i];
                max_sum = Math.max(max_sum, count);//每次累加都更新最大值
            } else {
                count = 0;
            }
            System.out.println(max_sum);
        }


    }

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int n;
int a[N];

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

var len=parseInt(readline());
var arr=readline().split(' ').map(Number);
var max=0;
if(arr.length==0){
    console.log(0)
}else if(arr.length==1){
    console.log(arr[0])
}else{
    var tem=0;
    // 关键在于；单个子串的和为负数时，这段子串也就无价值了！！！
    // 然后从下个索引开始计算和，当和>max时就改变max的值，得到最大的值
   for(var i=0;i<len;i++){
       tem+=arr[i];
       if(tem<0){
           tem=0;
       }else if(tem>max){
           max=tem;
       }
   }
   console.log(max)  
}

#include<cstdio>
(802)#include<vector>
using namespace std;
vector<int> v;
int main(){
    int n,dp,mmax;
    scanf("%d",&n);
    v.resize(n);
    for(int i=0;i<n;++i){
        scanf("%d",&v[i]);
    }
    mmax=v[0];
    dp=v[0];
    for(int i=1;i<n;++i)
    {
        dp=dp<0?v[i]:(dp+v[i]);
        mmax=max(dp,mmax);
    }
    printf("%d",mmax);
    return 0;
}

def SubListSum(arr):
    if len(arr) == 0:
        return
    if len(arr) == 1:
        return arr[0]
    maxsum = arr[0]
    maxendsum = arr[0]
    for i in range(1,len(arr)):
        maxendsum = max(arr[i],maxendsum+arr[i])
        maxsum = max(maxsum,maxendsum)
        
    return maxsum

N = eval(input())
ls = list(map(int, input().split()))
max_sum = 0 # 最大值
count = 0 # 累加和初始化
for i in range(len(ls)):
    if ls[i]+count > 0:
        count += ls[i]
        max_sum = max(max_sum, count) # 每次累加都更新最大值
    else:
        count = 0
print(max_sum)