题解 | 最大子段和 c#

using System;
using System.Collections.Generic;
using System.Linq;
public class Program {
    public static void Main() {

        int.TryParse(Console.ReadLine(), out int n);
        long[] nums = Console.ReadLine().Split(' ').Select(long.Parse).ToArray();
        Console.WriteLine(CaculateMaxSubArry(nums));

    }
    public static long CaculateMaxSubArry(long[] inputs) {
        long maxSoFar = inputs[0];
        List<long> dp = new List<long>();
        //先把dp填满，此时每个dp[i]表示以inputs[i]结尾的最大子数组和的最差情况
        for(int i = 0; i < inputs.Length; i++)
        {
            dp.Add(inputs[i]);
        }

        for (int i = 1; i < inputs.Length; i++)
        {
            //以input[i]结尾的最大子数组和，要么是input[i]本身(相当于开启一个新的子数组)，要么是input[i]加上以input[i-1]结尾的最大子数组和（相当于延续之前的子数组）
            long lastCaculation = dp[i-1];
            dp[i] = Math.Max(inputs[i], lastCaculation + inputs[i]);
            // dp[i] = lastCaculation + inputs[i];
            maxSoFar = Math.Max(maxSoFar, dp[i]);

        }
        return maxSoFar;
    }
}