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

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

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;
}

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

用动态规划来解，具体代码实现参考：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]

你假定的结果不正确。

示例：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();
}

 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;
    }

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

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(",");
    }

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(",");
}