每日OJ题_牛客_连续子数组最大和_线性dp_C++_Java

目录

牛客_连续子数组最大和_线性dp

题目解析

C++代码

Java代码

---

牛客_连续子数组最大和_线性dp

连续子数组最大和_牛客题霸_牛客网 (nowcoder.com)

描述：

        给定一个长度为 n的数组，数组中的数为整数。请你选择一个非空连续子数组，使该子数组所有数之和尽可能大，子数组最小长度为1。求这个最大值。

---

题目解析

• 状态表示： dp[i] 表示：以 i 位置为结尾的所有子数组中，最大和是多少。
• 状态转移方程： dp[i] = max(dp[i - 1] + arr[i], arr[i])

C++代码

#include <iostream>
#include <vector>
using namespace std;int main()
{int n = 0;cin >> n;vector<int> a(n);for(int i = 0; i < n; ++i){cin >> a[i];}vector<int> dp(n);int res = a[0];dp[0] = a[0];for(int i = 1; i < n; ++i){dp[i] = max(dp[i - 1] + a[i], a[i]);res = max(res, dp[i]);}cout << res << endl;return 0;
}

Java代码

import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main
{public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int[] arr = new int[n + 1];int[] dp = new int[n + 1];for(int i = 1; i <= n; i++){arr[i] = in.nextInt();}int ret = -101;for(int i = 1; i <= n; i++){dp[i] = Math.max(dp[i - 1], 0) + arr[i];ret = Math.max(ret, dp[i]);}System.out.println(ret);}
}