LeetCode -- Maximum Subarray
题目描述：
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.
在数组nums[]中找到连续子序列构成的最大和。
思路：
一道典型的DP题。
1.使用dp[i]来表示i位置所能达到的最大和
2.如果dp[i-1]+nums[i]大于nums[i]，则dp[i] = dp[i-1]+nums[i]；否则，dp[i] = nums[i]。
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.
在数组nums[]中找到连续子序列构成的最大和。
思路：
一道典型的DP题。
1.使用dp[i]来表示i位置所能达到的最大和
2.如果dp[i-1]+nums[i]大于nums[i]，则dp[i] = dp[i-1]+nums[i]；否则，dp[i] = nums[i]。
实现代码：
public class Solution {
public int MaxSubArray(int[] nums)
{
if(nums.Length == 0){
return 0;
}
var dp = new int[nums.Length];
dp[0] = nums[0];
for(var i = 1;i < nums.Length; i++){
if(dp[i-1] + nums[i] > nums[i]){
dp[i] = dp[i-1] + nums[i];
}
else{
dp[i] = nums[i];
}
}
return dp.Max();
}
}