LeetCode -- Maximum Subarray

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]。

實現代碼：

 

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();
    }
}