Skip to content

JAVA 数组中最长连续正数或负数子序列

Jump to bottom
CoderDream edited this page Jun 6, 2022 · 1 revision 
package com.keepsoft.devbase.business.util.demo.util;

public class FindList {

    public static void main(String[] args) {
        Double[] nums = {1.0, -3.0, 5.0, 7.0, 9.0, -6.0, -8.0, 10.0};
//        int result = findLengthOfLCIS(nums);
//        System.out.println(result);

        System.out.println("####上涨列表 : ");
        int[] result = findUpList(nums);
        for (int i = result[0]; i <= result[1]; i++) { //输出最长的递增子序列
            if(nums[i] > 0 ) {
                System.out.print(nums[i] + " ");
            }
        }
        System.out.println();
        System.out.println("####下降列表 : ");
        result = findDownList(nums);
        for (int i = result[0]; i <= result[1]; i++) { //输出最长的递增子序列
            if(nums[i] < 0 ) {
                System.out.print(nums[i] + " ");
            }
        }
        System.out.println();
    }

    public static int findLengthOfLCIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int ans = 1, start = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i + 1] > nums[i]) {
                /**
                 * 思路：
                 * 1.遍历一段连续递增序列后，执行else将连续序列开始位置
                 * 更新，并和上个连续序列长度比较，选出较长的序列长度。
                 *
                 * 2.i从0开始,i+1是下一个元素,遍历到len-2,i+1-start是
                 * 除了start位置之外的递增序列长度，需要+1，所以一段递增
                 * 序列长度为i+1-start+1
                 */
                ans = Math.max(ans, i + 1 - start + 1);
            } else {
                start = i + 1;
            }
        }
        return ans;
    }


    public static int[] findUpList(Double[] nums) {
        int h = 0;  //定义一个变量，用来储存正数序列最长的子序列，并且用于每一次的比较
        int left = 0, right = 0;    //储存最长子序列两头的下标
        for (int i = 0; i < nums.length - 1; i++) {
            int s = 0;  // 每次递增子序列的长度，并且每循环一次都归0
            for (int j = i + 1; j < nums.length; j++) {
                // 如果后面的数字小于等于0，那么直接跳出，进行下一次循环
               // System.out.println();
                if (0 >= nums[j]) {
                    break;
                }
                if (0 < nums[j]) {   //进行判断大小
                    s++;         //如果后面的比前面的数字大就自增1
                    if (s > h) {     //进行比较，如果最外层循环后一次大于前一次的递增子序列的长度
                        left = i;
                        right = j;   //那么最长子序列的下标就要改变，则赋值给left和right
                        h = s; //并且把s赋值给h，用于下一次比较
                    }
                }
            }
        }
//        for (int i = left; i <= right; i++) { //输出最长的递增子序列
//            if(nums[i] > 0 ) {
//                System.out.print(nums[i] + " ");
//            }
//        }
        // 修正
        if(nums[left] < 0 ) {
            left += 1;
        }

        if(nums[right] < 0 ) {
            right -= 1;
        }
//        System.out.println();

        return new int[]{left, right};
    }

    public static int[] findDownList(Double[] nums) {

        int h = 0;  //定义一个变量，用来储存正数序列最长的子序列，并且用于每一次的比较
        int left = 0, right = 0;    //储存最长子序列两头的下标
        for (int i = 0; i < nums.length - 1; i++) {
            int s = 0;  // 每次递增子序列的长度，并且每循环一次都归0
            for (int j = i + 1; j < nums.length; j++) {
                // 如果后面的数字小于等于0，那么直接跳出，进行下一次循环
               // System.out.println();
                if (0 <= nums[j]) {
                    break;
                }
                if (0 > nums[j]) {   //进行判断大小
                    s++;         //如果后面的比前面的数字大就自增1
                    if (s > h) {     //进行比较，如果最外层循环后一次大于前一次的递增子序列的长度
                        left = i;
                        right = j;   //那么最长子序列的下标就要改变，则赋值给left和right
                        h = s; //并且把s赋值给h，用于下一次比较
                    }
                }
            }
        }
//        for (int i = left; i <= right; i++) { //输出最长的递增子序列
//            if(nums[i] < 0 ) {
//                System.out.print(nums[i] + " ");
//            }
//        }
//
//        System.out.println();

        // 修正
        if(nums[left] > 0 ) {
            left += 1;
        }

        if(nums[right] > 0 ) {
            right -= 1;
        }
        return new int[]{left, right};
    }

    public static int[] findUpListInt(int[] nums) {
        int h = 0;  //定义一个变量，用来储存正数序列最长的子序列，并且用于每一次的比较
        int left = 0, right = 0;    //储存最长子序列两头的下标
        for (int i = 0; i < nums.length - 1; i++) {
            int s = 0;  // 每次递增子序列的长度，并且每循环一次都归0
            for (int j = i + 1; j < nums.length; j++) {
                // 如果后面的数字小于等于0，那么直接跳出，进行下一次循环
                // System.out.println();
                if (0 >= nums[j]) {
                    break;
                }
                if (0 < nums[j]) {   //进行判断大小
                    s++;         //如果后面的比前面的数字大就自增1
                    if (s > h) {     //进行比较，如果最外层循环后一次大于前一次的递增子序列的长度
                        left = i;
                        right = j;   //那么最长子序列的下标就要改变，则赋值给left和right
                        h = s; //并且把s赋值给h，用于下一次比较
                    }
                }
            }
        }
//        for (int i = left; i <= right; i++) { //输出最长的递增子序列
//            if(nums[i] > 0 ) {
//                System.out.print(nums[i] + " ");
//            }
//        }
        // 修正
        if(nums[left] < 0 ) {
            left += 1;
        }

        if(nums[right] < 0 ) {
            right -= 1;
        }
//        System.out.println();

        return new int[]{left, right};
    }

    public static int[] findDownListInt(int[] nums) {

        int h = 0;  //定义一个变量，用来储存正数序列最长的子序列，并且用于每一次的比较
        int left = 0, right = 0;    //储存最长子序列两头的下标
        for (int i = 0; i < nums.length - 1; i++) {
            int s = 0;  // 每次递增子序列的长度，并且每循环一次都归0
            for (int j = i + 1; j < nums.length; j++) {
                // 如果后面的数字小于等于0，那么直接跳出，进行下一次循环
                // System.out.println();
                if (0 <= nums[j]) {
                    break;
                }
                if (0 > nums[j]) {   //进行判断大小
                    s++;         //如果后面的比前面的数字大就自增1
                    if (s > h) {     //进行比较，如果最外层循环后一次大于前一次的递增子序列的长度
                        left = i;
                        right = j;   //那么最长子序列的下标就要改变，则赋值给left和right
                        h = s; //并且把s赋值给h，用于下一次比较
                    }
                }
            }
        }
//        for (int i = left; i <= right; i++) { //输出最长的递增子序列
//            if(nums[i] < 0 ) {
//                System.out.print(nums[i] + " ");
//            }
//        }
//
//        System.out.println();

        // 修正
        if(nums[left] > 0 ) {
            left += 1;
        }

        if(nums[right] > 0 ) {
            right -= 1;
        }
        return new int[]{left, right};
    }

    public static int findLengthOfLCIS3(int[] nums) {

        int h = 0;  //定义一个变量，用来储存递增序列最长的子序列，并且用于每一次的比较
        int left = 0, right = 0;    //储存最长子序列两头的下标
        for (int i = 0; i < nums.length - 1; i++) {
            int s = 0;  //来每次递增子序列的长度，并且每循环一次都归0
            for (int j = i + 1; j < nums.length; j++) {
                //如果后面的数字比前面的数字小于等于，那么直接跳出，进行下一次循环
                if (nums[j - 1] >= nums[j]) {
                    break;
                }
                if (nums[j - 1] < nums[j]) {   //进行判断大小
                    s++;         //如果后面的比前面的数字大就自增1
                    if (s > h) {     //进行比较，如果最外层循环后一次大于前一次的递增子序列的长度
                        left = i;
                        right = j;   //那么最长子序列的下标就要改变，则赋值给left和right
                        h = s; //并且把s赋值给h，用于下一次比较
                    }
                }
            }
        }
        for (int i = left; i <= right; i++) { //输出最长的递增子序列
            System.out.print(nums[i] + " ");
        }

        return 0;
    }
}

参考：JAVA-数组中最长连续递增子序列

Clone this wiki locally