贪心算法

在对问题求解时,总是做出在当前看来是最好的选择。不从整体最优上加以考虑,只做出在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。

解题的步骤:

1、建立数学模型来描述问题

2、把求解的问题分成若干个子问题

3、对每一子问题求解,得到子问题的局部最优解

4、把子问题的局部最优解合成原来问题的一个解

定义一个初始指针,指针向右移动,记录指针移动范围内最长连续递增序列的长度,指针移动到最后,就可以得出最长连续递增序列的长度

public class MaxSeq {

public static void main(String[] args) {

System.out.println(findLength(new int[]{1,2,3,3,4,2,5,6,7,8,9}));

}

private static int findLength(int[] nums) {

if (null == nums || nums.length == 0) return 0;

if (nums.length == 1) return 1;

// 定义初始的一个指针位置

int start = 0;

// 定义子数组的长度变量

int max = 0;

for (int i = 1; i < nums.length; i++) {

if (nums[i] <= nums[i-1]) {

// 移动start的位置

start = i;

}

max = Math.max(max, i – start + 1);

}

return max;

}

}

成哥java 想你所想 代码为本人代码 部分为来源网络 侵权请联系qq 522442116
成哥资源站 » 【算法】贪心算法

发表评论

提供最优质的资源集合

立即查看 了解详情