给定整数序列求连续子串最大和

import java.util.Scanner;

/**
 * Dynamic Programming
 *
 * State:
 *   dp[i]: 以a[i]为结尾的连续子串的最大和
 *
 * Initial State:
 *   dp[0] = a[0]
 *
 * State Transition:
 *   if (dp[i - 1] >= 0) dp[i] = dp[i - 1] + a[i];
 *   else dp[i] = a[i];
 *
 * @author wylu
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            String[] strs = scanner.nextLine().split(" ");
            int[] a = new int[strs.length];
            for (int i = 0; i < strs.length; i++) {
                a[i] = Integer.valueOf(strs[i]);
            }

            int[] dp = new int[a.length];
            dp[0] = a[0];
            int res = dp[0];
            for (int i = 1; i < a.length; i++) {
                dp[i] = (dp[i - 1] >= 0) ? dp[i - 1] + a[i] : a[i];
                res = Math.max(res, dp[i]);
            }
            System.out.println(res);
        }
    }
}

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

int main(){
    int x, s=0, Max=INT_MIN;
    while(scanf("%d", &x)!=EOF){
        s += x;
        Max = max(Max, s);
        if(s<0)
            s = 0;
    }
    printf("%d\n", Max);
    return 0;
}

if __name__ == '__main__':
    arr=list(map(int,input().split()))
    ans=min(arr)
    dp=[0] #判断将当前数加入子串还是从当前子串开始重新计算连续子串max(dp[-1]+a,a)  for a in arr:
        temp=max(dp[-1]+a,a)
        dp.append(temp)
        ans=max(ans,temp) print(ans)

#include "stdio.h"
#include "limits.h"
#include <iostream>
using namespace std;
int main()
{
    int num;
    int ans = INT_MIN;
    int sum = 0;
    while(cin>>num)
    {
        sum += num;
        ans = max(ans, sum);
        if(sum<0)
            sum=0;
    }
    cout<<ans<<endl;
    return 0;
}

package main

import (
    "fmt"
)

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

动态规划

• O(n)时间复杂度
• O(1)空间复杂度
• 状态转移方程为 d[i] = max(d[i-1]+arr[i], a[i])
• 用sum_tmp存储当前的d[i]
• 用sum_max存储当前d[0]到d[i]的最大值

a = input().split()
a = [int(a[i]) for i in range(len(a))]
def max_subsequence(arr):
    length = len(arr)
    if length == 0:
        return 0
    if length == 1:
        return arr[0]
    sum_tmp = arr[0]
    sum_max = arr[0]
    for i in range(1, length):
        sum_tmp = max(sum_tmp + arr[i], arr[i])
        if sum_max < sum_tmp:
            sum_max = sum_tmp
    return sum_max
print(max_subsequence(a))

while True:
    try:
        m = list(map(int,input().split()))
        sum = 0
        max = m[0]
        for i in m:
            if sum >= 0:
                sum += i
            else:
                sum = i
            if sum > max:
                max = sum
        print(max)
    except:
        break

def maxSum(l):
    if len(l) == 1:
        return l[0]
    dp = l[:]     # dp中最终存储的是以当前字符结尾的最大数字
    for i in range(1, len(l)):
        if dp[i-1] > 0:
            dp[i] = dp[i-1] + l[i]   # 前一位置和大于0，加下去，否则另起炉灶
    return max(dp)
    
if __name__ == "__main__":
    l = list(map(int, input().split()))
    print(maxSum(l))

//典型题目，因为是连续子串，因此我们根据当前位置是从头还是连续之前的来区分即可
#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;
int main(){
    vector<int> vec;
    int num;
    while(cin>>num)
        vec.push_back(num);
    int res=INT_MIN,cur=0;
    for(int i=0;i<vec.size();++i){
        cur=max(cur+vec[i],vec[i]); //进行当前位置是否连续的讨论
        res=max(res,cur);
    }
    cout<<res;
     return 0;
}
 

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

int main() {
    vector<int> vec;
    int a;
    while(cin>>a) {
        vec.push_back(a);
        if(cin.get() == '\n') break;
    }
    
    int size = vec.size();
    int max = vec[0], cursum = vec[0];
    
    for(int i = 1; i < size; i++){
        cursum = cursum + vec[i] > vec[i] ? cursum + vec[i] : vec[i];
        max = cursum > max ? cursum : max;
    }
    
    cout<<max<<endl;
    
    return 0;
}

num=input()
num_list=[int(n) for n in num.split()]
temp=0
max_value=-100000
for i in range(len(num_list)):
    temp=max(temp+num_list[i],num_list[i])
    max_value=max(max_alue,temp)
print(max_value)

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>


int FindGreatestSumOfSubArray(vector<int> array) {
        int len = array.size();
        if(len == 0)
            return 0;        //如果数组长度为0,返回0
        if(len == 1)
            return array.front();    //如果数组长度为1,返回唯一的元素
        vector<int> sum;    //存储数组每次累加的和值
        int max;    //最大的那个和值
        int i,j;        
        for(i = 0; i < len-1; i++)    //i从0到倒数第二位置
        {
            sum.push_back(array[i]);        //将数组首元素赋值给sum
            for(j = i+1; j < len; j++)
                sum.push_back(sum.back() + array[j]);    //将sum的最后一个元素和下一个数组元素进行相加,并插入到sum最后
        }
        sort(sum.begin(),sum.end());    //对每轮得到的和值进行排序,然后找到该轮的和的最大值
        max = sum.back();
        return max;
}

int main(void)
{
    vector<int> data;
    int swp;
   while(cin>>swp)
       data.push_back(swp);
    cout<<FindGreatestSumOfSubArray(data);
    return 0;
}