目录
牛客_连续子数组最大和_线性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);}
}