weixin_42042460
weixin_42042460
采纳率63.6%
2018-04-22 11:54 阅读 1.4k
已采纳

如果求最大非连续子序列??

40

假设有一个序列是L = [1, 0, 5, 3, 2, 7, 9, 15, 6, 4, 13]
他的最大非连续子序列就是 S = [1, 5, 7, 15, 13] 俩俩数字任意不相邻
现在要求给L求S

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享

9条回答 默认 最新

  • 已采纳
    feelcycle_07 默默悟问 2018-04-22 15:33
    public static List<Integer> longest_increasing_subsequence(List<Integer> sequence) {
        // Write your solution here
        if (sequence.isEmpty()) return new ArrayList<Integer>();
        int max_size[] = new int[sequence.size()];
        int prev_index[] = new int[sequence.size()];
        max_size[0] = 1;
        prev_index[0] = -1;
        for (int i = 1; i < sequence.size(); i++) {
            int cur_max = 1;
            int cur_prev = -1;
            int iVal = sequence.get(i);
            for (int j = i - 1; j >= 0; j--) {
                if (cur_max < max_size[j] + 1 && sequence.get(j) < iVal) {
                    cur_max = max_size[j] + 1;
                    cur_prev = j;
                }
            }
            prev_index[i] = cur_prev;
            max_size[i] = cur_max;
        }
        int max_idx = sequence.size() - 1;
        int max_val = max_size[max_idx];
        for (int i = max_idx - 1; i >= 0; i--) {
            if (max_val < max_size[i]) {
                max_idx = i;
                max_val = max_size[i];
            }
        }
        List<Integer> aList = new ArrayList<Integer>();
        int idx = max_idx;
        aList.add(sequence.get(idx));
        while (prev_index[idx] >= 0) {
            idx = prev_index[idx];
            aList.add(sequence.get(idx));
        }
        List<Integer> retList = new ArrayList<Integer>(aList.size());
        for (int i = aList.size() - 1; i >= 0; i--) {
            retList.add(aList.get(i));
        }
        return retList;
    }
    
    点赞 评论 复制链接分享
  • flonny 精锐小菜鸡 2018-04-23 06:58
    public static String[] getMaxSubArray(int[] arr) {
            String[] strArr = new String[arr.length];
            for(int i =0;i<arr.length;i++) {
                strArr[i] = String.valueOf(arr[i]);
            }
            for(int i=2;i<arr.length;i++) {
                if (arr[i-2] + arr[i] > arr[i-1]) {
                    arr[i] = arr[i-2] + arr[i];
                    strArr[i] = strArr[i-2]+","+strArr[i];
                } else {
                    arr[i] = arr[i-1];
                    strArr[i] = strArr[i-1];
                }
            }
            return strArr[strArr.length-1].split(",");
        }
    
    
    点赞 1 评论 复制链接分享
  • qq_31372571 qq_31372571 2018-04-22 13:05

    状态转移方程:dp[i]=max(dp[i-1],dp[i-2]+dp[i])

    点赞 评论 复制链接分享
  • caozhy 从今以后生命中的每一秒都属于我爱的人 2018-04-22 14:44

    用动态规划来解,具体代码实现参考:https://www.jianshu.com/p/04c03059e538

    点赞 评论 复制链接分享
  • feelcycle_07 默默悟问 2018-04-22 17:04

    改造很简单:

    private static boolean isValueNotNextInArray(List<Integer> sequence, int ival, int cur_prev, int[] prev_index) {
        while(cur_prev >= 0) {
            int prev_val = sequence.get(cur_prev);
            if (Math.abs(ival - prev_val) == 1) return false;
            cur_prev = prev_index[cur_prev];
        }
        return true;
    }
    
    public static List<Integer> longest_notnext_subsequence(List<Integer> sequence) {
        // Write your solution here
        if (sequence.isEmpty()) return new ArrayList<Integer>();
        int max_size[] = new int[sequence.size()];
        int prev_index[] = new int[sequence.size()];
        max_size[0] = 1;
        prev_index[0] = -1;
        for (int i = 1; i < sequence.size(); i++) {
            int cur_max = 1;
            int cur_prev = -1;
            int iVal = sequence.get(i);
            for (int j = i - 1; j >= 0; j--) {
                if (cur_max < max_size[j] + 1 && isValueNotNextInArray(sequence, iVal, j, prev_index)) {
                    cur_max = max_size[j] + 1;
                    cur_prev = j;
                }
            }
            prev_index[i] = cur_prev;
            max_size[i] = cur_max;
        }
        int max_idx = sequence.size() - 1;
        int max_val = max_size[max_idx];
        for (int i = max_idx - 1; i >= 0; i--) {
            if (max_val < max_size[i]) {
                max_idx = i;
                max_val = max_size[i];
            }
        }
        List<Integer> aList = new ArrayList<Integer>();
        int idx = max_idx;
        aList.add(sequence.get(idx));
        while (prev_index[idx] >= 0) {
            idx = prev_index[idx];
            aList.add(sequence.get(idx));
        }
        List<Integer> retList = new ArrayList<Integer>(aList.size());
        for (int i = aList.size() - 1; i >= 0; i--) {
            retList.add(aList.get(i));
        }
        return retList;
    }
    

    public static void testLongArray() {
    List vals = longest_notnext_subsequence(Arrays.asList(1, 0, 5, 3, 2, 7, 9, 15, 6, 4, 13));
    System.out.println(vals);
    }

    public static void main(String args[]) {
    testLongArray();
    }

    结果是:
    [0, 5, 2, 7, 9, 15, 13]
    
    你假定的结果不正确。
    
    点赞 评论 复制链接分享
  • weixin_39521929 以伽利略之名 2018-04-22 17:57

    示例:C#
    static List GetMaxSeq(List list)
    {
    List res = new List();
    List ou = new List();
    List qi = new List();
    for (int i = 0; i < list.Count; i++)
    {
    if (i%2==0) //奇偶分裂,奇偶数列都是连续不相邻的
    {
    ou.Add(list[i]);
    }
    else
    {
    qi.Add(list[i]);
    }
    }
    int last = 0;
    for (int i = 0; i < qi.Count; i++)
    {
    if (ou[i] {
    ou[i] = qi[i]; // 在相等位置上将奇列中大于偶列中的数替换到偶列
    last = i;
    }
    }
    for (int i = 0; i {
    if (i!=last+1) // 记录最后的替换位置,防止替换后结果连续,那么即排除奇最后位+1的偶数,在原数列奇偶相等时还需判断是否超索引
    {
    res.Add(ou[i]);
    }
    }
    return res;
    }
    static void OutList(List list)
    {
    string res = "";
    foreach (T item in list)
    {
    res += item + " ";
    }
    Console.WriteLine(res);
    }
    static int[] InPutToArr(string line)
    {
    string[] nums=line.Split(',');
    int[] res=new int[nums.Length ];
    for (int i = 0; i < nums.Length; i++)
    {
    res[i] = int.Parse(nums[i]);
    }
    return res;
    }
    static void Main(string[] args)
    {
    string line = Console.ReadLine();
    while (!line.Trim().Contains("quit"))
    {
    int[] arr = InPutToArr(line);
    List input = new List(arr);
    List output = GetMaxSeq(input);
    OutList(output);
    line = Console.ReadLine();
    }
    //string line = "1,0,5,3,2,7,9,15,6,4,13";

    Console.ReadLine();
    }
    图片说明

    点赞 评论 复制链接分享
  • flonny 精锐小菜鸡 2018-04-23 03:23
     public static Integer[] getMaxSubArray(int[] arr) {
            List<Integer> list = new ArrayList<Integer>();
            int index = 0;
            do {
                list.add(arr[index]);
                if(index+2 >= arr.length)
                    break;
                if(index+2 < arr.length && index+3 >= arr.length) {
                    list.add(arr[index+2]);
                    break;
                }
                if(arr[index+2] >= arr[index+3])
                    index += 2;
                else
                    index += 3;
            } while(index<arr.length);
    
            Integer[] resultArray = new Integer[list.size()];
            list.toArray(resultArray);
            return resultArray;
        }
    
    点赞 评论 复制链接分享
  • feelcycle_07 默默悟问 2018-04-23 06:15

    被你的描述迷惑了,这个应该没问题了:
    public static List longest_maxval_subsequence(List sequence) {
    // Write your solution here
    if (sequence.isEmpty()) return new ArrayList();
    int max_vals[] = new int[sequence.size()];
    int prev_index[] = new int[sequence.size()];
    max_vals[0] = sequence.get(0);
    prev_index[0] = -1;
    for (int i = 1; i < sequence.size(); i++) {
    int cur_max = sequence.get(i);
    int cur_prev = -1;
    int iVal = sequence.get(i);
    for (int j = i - 2; j >= 0; j--) {
    if (cur_max < max_vals[j] + iVal) {
    cur_max = max_vals[j] + iVal;
    cur_prev = j;
    }
    }
    prev_index[i] = cur_prev;
    max_vals[i] = cur_max;
    }
    int max_idx = sequence.size() - 1;
    int max_val = max_vals[max_idx];
    for (int i = max_idx - 1; i >= 0; i--) {
    if (max_val < max_vals[i]) {
    max_idx = i;
    max_val = max_vals[i];
    }
    }
    List aList = new ArrayList();
    int idx = max_idx;
    aList.add(sequence.get(idx));
    while (prev_index[idx] >= 0) {
    idx = prev_index[idx];
    aList.add(sequence.get(idx));
    }
    List retList = new ArrayList(aList.size());
    for (int i = aList.size() - 1; i >= 0; i--) {
    retList.add(aList.get(i));
    }
    return retList;
    }

    点赞 评论 复制链接分享
  • flonny 精锐小菜鸡 2018-04-24 07:01
    public static String[] getMaxSubArray(int[] arr) {
            String[] strArr = new String[arr.length];
            for(int i =0;i<arr.length;i++) {
                strArr[i] = String.valueOf(arr[i]);
            }
            for(int i=1;i<arr.length;i++) {
                if(i<2) {
                    if (arr[i-1] > arr[i]) {
                        arr[i] = arr[i - 1];
                        strArr[i] = strArr[i-1];
                    }
                    continue;
                }
                if (arr[i-2] + arr[i] > arr[i-1]) {
                    arr[i] = arr[i-2] + arr[i];
                    strArr[i] = strArr[i-2]+","+strArr[i];
                } else {
                    arr[i] = arr[i-1];
                    strArr[i] = strArr[i-1];
                }
            }
            return strArr[strArr.length-1].split(",");
    }
    
    
    点赞 评论 复制链接分享

相关推荐