贪心算法

例题

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,分治法

见分治法文章。