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

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

9个回答

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;
}
feelcycle_07
默默悟问 回复weixin_42042460: 已经答了
2 年多之前 回复
weixin_42042460
weixin_42042460 回复feelcycle_07: 我开了个新问题,你试出来了可以来答
2 年多之前 回复
feelcycle_07
默默悟问 回复weixin_42042460: 应该可以,回头我试下
2 年多之前 回复
weixin_42042460
weixin_42042460 可以用分治法吗,我再开个新的
2 年多之前 回复
feelcycle_07
默默悟问 以为是求最大升序数列了
2 年多之前 回复
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(",");
    }

weixin_42042460
weixin_42042460 回复flonny: 这个能用分治来做吗
2 年多之前 回复
flonny
精锐小菜鸡 回复weixin_42042460: 的确,我直接跳过了前两个参数,是有点问题,我再优化一下吧。
2 年多之前 回复
weixin_42042460
weixin_42042460 你的结果是2,8 正确的应该是5,8
2 年多之前 回复
weixin_42042460
weixin_42042460 arr={5,2,1,8}
2 年多之前 回复
weixin_42042460
weixin_42042460 这个可以的,可以把字符串数组换成list来存吗?
2 年多之前 回复
flonny
精锐小菜鸡 两个数组,一个做int的sum运算和对比,另一个做字符串拼接
2 年多之前 回复

被你的描述迷惑了,这个应该没问题了:
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;
}

feelcycle_07
默默悟问 回复weixin_42042460: 这个就是动态规划
2 年多之前 回复
weixin_42042460
weixin_42042460 你这个是分治法?
2 年多之前 回复
feelcycle_07
默默悟问 List<Integer> vals = longest_maxval_subsequence(Arrays.asList(1, 0, 5, 3, 2, 7, 9, 15, 6, 4, 13)); System.out.println(vals);
2 年多之前 回复
feelcycle_07
默默悟问 回复feelcycle_07: List模版带Integer的,系统没显示出来
2 年多之前 回复
feelcycle_07
默默悟问 输出是:[1, 5, 7, 15, 13]
2 年多之前 回复

示例: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();
}
图片说明

weixin_42042460
weixin_42042460 回复weixin_39521929: 我会再开一个问题,你的qq多少
2 年多之前 回复
weixin_39521929
以伽利略之名 回复weixin_42042460: 没漏的,不知哪里漏了,你是完全不懂代码的吗,我怎么重发给你,你给个啥QQ,微信邮件联系方式,我发源码给你
2 年多之前 回复
weixin_42042460
weixin_42042460 代码有的地方漏了吧,能发个有格式的嘛
2 年多之前 回复
 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;
    }
weixin_42042460
weixin_42042460 回复flonny: 问题就是dp只能求出最大和,不能求出每个数字把
2 年多之前 回复
flonny
精锐小菜鸡 回复weixin_42042460: 好吧,的确是要用动态规划:dp[i] = max(dp[i-2]+dp[i], dp[i-1])
2 年多之前 回复
weixin_42042460
weixin_42042460 0,100,5,3,2,7,9,15这个就错了,你这个是首先把第一项加进去吧,如果第二项比第一个大呢?
2 年多之前 回复

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

weixin_42042460
weixin_42042460 这个是求最大值的,如何记录每个数呢
2 年多之前 回复

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

改造很简单:

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]

你假定的结果不正确。
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(",");
}

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问