每日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);
    }
}