贪心算法
例题
1，最大子序和
来自LeetCode 53
解法
1，贪心
- 根据题意我们可以发现这样一个贪心思想：当前面子序列和小于0时，不如从自身重新开始计算。
- 边界条件（所有数都是负数时），应该考虑此时的值不为0，而是为最小的数。
class Solution {
public int maxSubArray(int[] nums) {
int max = -Integer.MAX_VALUE;
int temp = 0;
for(int i = 0;i<nums.length;i++){
if(temp<0)
temp = 0;
temp+=nums[i];
max = Math.max(temp,max);
}
return max;
}
}2，动态规划
见动态规划文章。
3，分治法
见分治法文章。
正文完