9个回答

``````public static List<Integer> longest_increasing_subsequence(List<Integer> sequence) {
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;
while (prev_index[idx] >= 0) {
idx = prev_index[idx];
}
List<Integer> retList = new ArrayList<Integer>(aList.size());
for (int i = aList.size() - 1; i >= 0; i--) {
}
return retList;
}
``````

2 年多之前 回复
weixin_42042460 回复feelcycle_07: 我开了个新问题，你试出来了可以来答
2 年多之前 回复

2 年多之前 回复
weixin_42042460 可以用分治法吗，我再开个新的
2 年多之前 回复

2 年多之前 回复

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

``````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) {
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;
while (prev_index[idx] >= 0) {
idx = prev_index[idx];
}
List<Integer> retList = new ArrayList<Integer>(aList.size());
for (int i = aList.size() - 1; i >= 0; 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]

``````

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) //奇偶分裂，奇偶数列都是连续不相邻的
{
}
else
{
}
}
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的偶数，在原数列奇偶相等时还需判断是否超索引
{
}
}
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)
{
while (!line.Trim().Contains("quit"))
{
int[] arr = InPutToArr(line);
List input = new List(arr);
List output = GetMaxSeq(input);
OutList(output);
}
//string line = "1,0,5,3,2,7,9,15,6,4,13";

}

weixin_42042460 回复weixin_39521929: 我会再开一个问题，你的qq多少
2 年多之前 回复

2 年多之前 回复
weixin_42042460 代码有的地方漏了吧，能发个有格式的嘛
2 年多之前 回复
`````` public static Integer[] getMaxSubArray(int[] arr) {
List<Integer> list = new ArrayList<Integer>();
int index = 0;
do {
if(index+2 >= arr.length)
break;
if(index+2 < arr.length && index+3 >= arr.length) {
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 回复flonny: 问题就是dp只能求出最大和，不能求出每个数字把
2 年多之前 回复

2 年多之前 回复
weixin_42042460 0,100,5,3,2,7,9,15这个就错了，你这个是首先把第一项加进去吧，如果第二项比第一个大呢？
2 年多之前 回复

public static List longest_maxval_subsequence(List sequence) {
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;
while (prev_index[idx] >= 0) {
idx = prev_index[idx];
}
List retList = new ArrayList(aList.size());
for (int i = aList.size() - 1; i >= 0; i--) {
}
return retList;
}

2 年多之前 回复
weixin_42042460 你这个是分治法？
2 年多之前 回复

2 年多之前 回复

2 年多之前 回复

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 回复flonny: 这个能用分治来做吗
2 年多之前 回复

2 年多之前 回复
weixin_42042460 你的结果是2，8 正确的应该是5，8
2 年多之前 回复
weixin_42042460 arr={5,2,1,8}
2 年多之前 回复
weixin_42042460 这个可以的，可以把字符串数组换成list来存吗？
2 年多之前 回复

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

``````