Task4最大子序和

一、题目

• 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

二、思路

• 最野蛮的想法，从正数的元素开始，两层for循环，对所有子区间求和。

public class Solution {
   public int MaxSubArray(int[] nums)
   {
       
       int maxSum=nums[0];
       if(nums.Max()<=0) maxSum=nums.Max();
       for(int i=0;i<nums.Length;i++)
         {if(nums[i]>0)
           {
           int sum=0;
           for(int j=i;j<nums.Length;j++)
           {
               sum+=nums[j];
               maxSum=Math.Max(maxSum,sum);
           }
           }
         }
         return maxSum;
   }
}

• 以每一个位置为子数组的末位，用该位置的最大子数组和替换该位置的元素。以此方法更新原数组，以maxSum标记最大子数组和。

  public class Solution
    {
        public int MaxSubArray(int[] nums)
        {
            int maxSum = nums[0];
            for (int i = 1; i < nums.Length; i++)
            {
                if (nums[i - 1] > 0)
                {
                    nums[i] += nums[i - 1];
                }
                maxSum = Math.Max(nums[i], maxSum);
            }
           
            return maxSum;
        }
    }