思路：搜索

定义$dfs(l,r,sum)$表示当前左边界为$l$（不包含），有边界为$r$（不包含），总计和为$sum$的情况。

则下一步考虑向左或者向右搜索，即$dfs(l-1,r,sum+a[l])$或者$dfs(l,r+1,sum+a[r])$。

当然，$l$和$r$不能超过数组的左右边界。

由于$1\le a_i\le 10^9$，且每次均只能加比自己大的数，因此最多仅能扩展30次($2^{30}=1073741824$)

代码

C++

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

const int maxn=1e5+10;
int n;
ll a[maxn];
ll mx=LLONG_MIN;

void dfs(int l,int r,ll sum){
	mx = max(mx, sum);
	if(l>=1&&a[l]>sum){
		dfs(l-1,r,sum+a[l]);
	}
	if(r<=n&&a[r]>sum){
		dfs(l,r+1,sum+a[r]);
	}
}

int main() {
    std::ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;++i){
    	cin>>a[i];
	}
	for(int i=1;i<=n;++i){
		mx=LLONG_MIN;
		dfs(i-1,i+1,a[i]);
		cout<<mx<<" ";
	}
	 
    return 0;
}

java

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for(int i = 0 ; i < n ; i ++) a[i] = sc.nextInt();
        StringJoiner ans = new StringJoiner(" ");
        for(int i = 0 ; i < n ; i ++) {
            ans.add("" + dfs(a, i-1, i+1, (long)a[i]));
        }
        System.out.println(ans);
    }
    static long dfs(int[] a, int left, int right, long now) {
        long ans = now;
        if(left >= 0 && a[left] > now)
            ans = dfs(a, left-1, right, now+a[left]);
        if(right < a.length && a[right] > now)
            ans = Math.max(ans, dfs(a, left, right+1, now+a[right]));
        return ans;
    }
}

python

import sys
from collections import *
from functools import *


n=int(sys.stdin.readline().strip())
ll=list(map(int,sys.stdin.readline().strip().split()))
maxx=float('-inf')
def dfs(l,r,now):
    global maxx
    maxx=max(maxx,now)
    if l>=0 and ll[l]>now:
        dfs(l-1,r,now+ll[l])
    if r<n and ll[r]>now:
        dfs(l,r+1,now+ll[r])

for i in range(n):
    maxx=float('-inf')
    dfs(i-1,i+1,ll[i])
    print(maxx,end=' ')

题目内容

给出一个长度为$n$的数组$a_1,a_2,...,a_n$，假如你从$x$点出发（初始区间为$[x,x]$，初始价值为$a_x$），每到

达一个点就把这个点加入到区间内并获得当前点的价值，每次能将当前所拥有的区间向右或者向左扩展

一个（不能超过边界），且被拓展的位置的值一定要大于当前所拥有的价值之和。

输出对于起点$x=1,2,...,n$，答案分别是多少。

输入描述

第一行正整数$n$，表示数组的长度。

接下来一行$n$个正整数代表$a_1,a_2,...,a_n$。

$1≤ n≤ 10^5$，$1≤ a_i≤ 10^9$

输出描述

输出一行$n$个数字代表答案。

示例 1

输入

3
2 1 4

输出

2 7 4

说明

从$1,3$出发只能在自己$2$出发先变成$[1,2]$，再变成$[2,3]$

示例2

输入

5
2 3 6 1 4

输出

11 9 6 11 4