使用贪心算法解决“最长连续递增序列”问题

最长连续递增序列
给定一个未经排序的整数数组，找到最长且连续递增的子序列，并返回该序列的长度。
连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], …, nums[r – 1], nums[r]] 就是连续递增子序列。
示例 1：
输入：nums = [1,3,5,4,7]
输出：3
解释：最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。
示例 2：
输入：nums = [2,2,2,2,2]
输出：1
解释：最长连续递增序列是 [2], 长度为1。
分析：
从0开始寻找递增序列，并将长度记录，记录递增序列的最后一个下标，然后从该下标继续寻找，记录长度，取长度最大的即可。
贪心算法（greedy algorithm，又称贪婪算法）
是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。
贪心算法一般按如下步骤进行：
1、建立数学模型来描述问题。
2、把求解的问题分成若干个子问题。
3、对每个子问题求解，得到子问题的局部最优解。
4、把子问题的解局部最优解合成原来解问题的一个解。
贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择。

package od1;

/**
 * 最长连续递增序列（贪心.算法）
 * 给定一个未经排序的整数数组，找到最长且连续递增的子序列，并返回该序列的长度。
 * 原文地址：https://www.codernav.com/2848.html
 * 更多算法详解：https://www.codernav.com
 */
public class OdTest33 {
    public static void main(String[] args) {
        // 贪心.算法
        int length = f(new int[]{1, 2, 3, 2, 3, 4, 3, 4, 5, 6, 7});
        System.out.println(length);
    }

    private static int f(int[] nums) {
        if (nums.length == 1) {
            return 1;
        }
        // 记录长度
        int length = 0;
        // 开始下标
        int start = 0;
        // 通过i来计数
        for (int i = 1; i < nums.length; i++) {
            // 如果元素小于等于前一个元素，递增区间终止
            if (nums[i] <= nums[i - 1]) {
                start = i;
            }
            // 区间长度的计算公式：i-start+1
            length = Math.max(length, i - start + 1);
        }
        return length;
    }
}