首页 > 试题广场 >

连续子数组最大和

[编程题]连续子数组最大和
  • 热度指数:27940 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

输入一个整形数组(可能有正数和负数),求数组中连续子数组(最少有一个元素)的最大和。要求时间复杂度为O(n)。


输入描述:
【重要】第一行为数组的长度N(N>=1)

接下来N行,每行一个数,代表数组的N个元素


输出描述:
最大和的结果
示例1

输入

8
1
-2
3
10
-4
7
2
-5

输出

18

说明

最大子数组为 3, 10, -4, 7, 2
头像 猜猜我是谁⊙∀⊙!
发表于 2019-08-05 23:49:43
#普通的DP 问题 if __name__ == "__main__": n = int(input()) l = [] for _ in range(n): l.append(int(input())) s = [0 for _ in range(n 展开全文
头像 玩物尚智
发表于 2020-07-16 08:27:31
    这道题最容易想到的解决方案是O(N2)时间复杂度的解决方案,建立一个二维数组,记录所有以ai开头aj结尾的子数组的和,并找出他们的最大值。可能是牛客网测试数据数据量不够大,这个解决方案的代码也能AC,居然没有超时。因为方案太简单了,这个方案的代码就不贴 展开全文
头像 代码杀我
发表于 2020-06-30 09:18:02
动态规划没想出来,想出来一个前缀和找最大区间和的方法;第二个for循环里边记录已遍历点之前的最小值,方便后续做差寻找最大区间和;注意第二个for循环从0开始(否则类似1 2 3 4 5 6判断不全),最后特判n==0输出; #include<bits/stdc++.h> using na 展开全文
头像 ElonB
发表于 2019-09-29 19:34:45
""" 动态规划,连续子序列的最大和 dp[i]为i为结束点的子序列最大和 """ if __name__ == '__main__':     n = int(input())   &nb 展开全文
头像 白色高跟鞋
发表于 2020-04-29 00:30:36
DP的核心思想是,如果以i为终止序号的某个连续序列最大和小于0,那么下一个输入加上一个负数必然小于此输入,于是干脆另起炉灶直接赋值改输入;否则,则一个正数加上该输入,最终结果都要比单纯使用该输入要大。【即把连续序列的和直接当成一个数跟下一个输入进行对比】 N = int(input()) dp = 展开全文
头像 想找工作的菜鸡啊
发表于 2023-10-15 01:09:53
import sys def MaxNum(n, lis): k = [0 for _ in range(n)] k[0] = lis[0] for i in range(1, n): k[i] = max(lis[i],k[i-1] + lis[i]) 展开全文
头像 牛客245611291号
发表于 2020-05-27 20:58:50
import java.util.Scanner; public class Main{ public static void main(String[] args){ Scanner in = new Scanner(System.in); int n = 展开全文
头像 咕咚选手
发表于 2023-04-21 00:21:08
#include <climits> #include <iostream> #include <vector> using namespace std; int main() { int buf, n; cin >> n; 展开全文
头像 靠近1
发表于 2023-10-04 13:04:43
#include <iostream> #include<vector> #include<algorithm> using namespace std; int main() { vector<int> v; int N; cin 展开全文
头像 能奈
发表于 2021-10-11 17:35:28
N=int(input()) l=[] for i in range(N): l.append(int(input())) if max(l)<0: print(max(l)) else: sum=0 a=[] for i in range(len(l) 展开全文