【2.19】算法题2：贪心算法、动态规划、分治

题目：给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组 是数组中的一个连续部分。

方法一：贪心算法

原理：若当前指针所指元素之前的和小于0，则丢弃当前元素之前的数列。

三个变量： 前面数之和 当前数之和 最大和

int maxSubArray(int* nums, int numsSize){int preSum = 0,MaxSum = -10000,curSum = nums[0]; //初始化之前和为0，当前和为第一个元素，最大和为一个很大的负数。for(int i = 0;i < numsSize;i ++){  //遍历数组if(i==0) preSum = 0;else preSum += nums[i-1];if(preSum<0){   //如果之前和小于0，则把当前元素赋值给当前和，之前和重新变为0curSum = nums[i]; preSum = 0;}else{curSum = preSum + nums[i]; //如果之前和不小于0，则把当前元素+之前和赋值给当前和，}if(curSum>MaxSum){  //如果当前和大于最大和，则赋值给最大和MaxSum = curSum;}}return MaxSum;
}

复杂度：时间O(n)，空间O(1)。

方法二：动态规划

若前一个元素大于0，则将其加到当前元素上。

int maxSubArray(int* nums, int numsSize) {int pre = 0, maxAns = nums[0];  //初始化前一个元素为0，最大子数组为0for (int i = 0; i < numsSize; i++) { //遍历数组pre = fmax(pre + nums[i], nums[i]);//返回两个数中最大的数，赋值给前一个元素maxAns = fmax(maxAns, pre);//每一个当前元素和当前最大子数组和比较}return maxAns;
}

动态规划适用场景：

能够利用动态规划算法求解的问题都会具备以下两点性质：

1. 最优子结构： 利用动态规划算法求解问题的第一步就是需要刻画问题最优解的结构，并且如果一个问题的最优解包含其子问题的最优解，则此问题具备最优子结构的性质。因此，判断某个问题是否适合用动态规划算法，需要判断该问题是否具有最优子结构。

Tips: 最优子结构的定义主要是在于当前问题的最优解可以从子问题的最优解得出，当子问题满足最优解之后，才可以通过子问题的最优解获得原问题的最优解。

2. 重叠子问题： 适合用动态规划算法去求解的最优化问题应该具备的第二个性质是问题的子问题空间必须足够” 小 “，也就是说原问题递归求解时会重复相同的子问题，而不是一直生成新的子问题。如果原问题的递归算法反复求解相同的子问题，我们就称该最优化问题具有重叠子问题。

Tips: 在这里，我们需要注意是，与适用动态规划算法去求解的问题具备重叠子问题性质相反，前面我们介绍的分治算法递归解决问题时，问题的子问题都是互不影响，相互独立的，这个也是我们在选用动态规划算法还是分治法解决问题时的一个判断条件。

时间复杂度：O(n)，其中 n 为 nums 数组的长度。我们只需要遍历一遍数组即可求得答案。

空间复杂度：O(1)。我们只需要常数空间存放若干变量。

注：和贪心算法一样，动态规划算法只是一种思想，不是像排序算法一样有具体的代码。

方法三：分治算法

分治算法（Divide and Conquer）

1. 将序列从中分为左右两个子序列。

2. 递归求得两个子列的最大和。

3. 从中分点分头向左、右两边扫描，找出跨过分界线的最大子列和。

4. 输出这三个子列和最大的一个。

struct Status {int lSum, rSum, mSum, iSum;
};struct Status pushUp(struct Status l, struct Status r) {int iSum = l.iSum + r.iSum;int lSum = fmax(l.lSum, l.iSum + r.lSum);int rSum = fmax(r.rSum, r.iSum + l.rSum);int mSum = fmax(fmax(l.mSum, r.mSum), l.rSum + r.lSum);return (struct Status){lSum, rSum, mSum, iSum};
};struct Status get(int* a, int l, int r) {if (l == r) {return (struct Status){a[l], a[l], a[l], a[l]};}int m = (l + r) >> 1;struct Status lSub = get(a, l, m);struct Status rSub = get(a, m + 1, r);return pushUp(lSub, rSub);
}int maxSubArray(int* nums, int numsSize) {return get(nums, 0, numsSize - 1).mSum;
}