最大子数组和

1.LeetCode原题地址

2.解法思路一：暴力求解，这个是很简单的，内嵌遍历循环就可以了

public class Solution {
    public int MaxSubArray(int[] nums) {
        int max = int.MinValue;
        for(int i = 0 ;i<nums.Length;i++){
            int temp = 0;
            for(int j = i ; j < nums.Length; j++){
                temp += nums[j];
                if(temp>=max)
                    max = temp;
            }

        }
        return max;
    }
}

3.解法思路二：动态规划，通过枚举迭代的方式，自底向上，所以必然会得到最优解，但是在迭代或者递归的过程中，动态规划会将一些重复的遍历计算的结果进行保存，也被称为带”备忘录“的递归。

通常跟最大最小值有关的，都需要初始化为极大值或极小值
记录一个temp临时变量，也就相当于备忘录，由于这里”连续的子数组“这一个特殊性，原本就可以省去很多的遍历，所以可以用一个temp记录num[i]前的和即可，不需要再申明一个集合了，在空间上进行优化。
最关键的来了，也就是动态规划的状态转移方程，如果temp记录的子数组和+当前数之和小于记录的子数组和，那么重新开始寻找子数组；
temp记录的之前的最大值会赋值给max变量，所以即使temp变量遗失了也没有关系；

public class Solution {
    public int MaxSubArray(int[] nums) {
        int max = int.MinValue;
        int len = nums.Length;

        int temp = 0;
        for(int i =0 ; i< len ;i++){
            temp = Math.Max(temp+nums[i],nums[i]);
            max = Math.Max(max,temp);
        }

        return max;
    }
}

4.解法思路四：贪心算法本身就是动态规划一个特例，在这里的应用也和动态规划很像，关键就是找出贪心算法的抉择。

public class Solution {
    public int MaxSubArray(int[] nums) {
        int max = int.MinValue;
        int len = nums.Length;

        int temp = 0;
        for(int i =0 ; i< len ;i++){
            temp += nums[i];
            max = Math.Max(max,temp);
            if(temp < 0)
                temp = 0;
        }

        return max;
    }
}

5.解法思路三：分治法