weixin_42042460

2018-04-22 11:54 阅读 1.4k

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

40

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

9条回答默认 最新

• 已采纳
默默悟问 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;
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;
}
``````
点赞 评论 复制链接分享
• 精锐小菜鸡 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 2018-04-22 13:05

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

点赞 评论 复制链接分享
• 用动态规划来解，具体代码实现参考：https://www.jianshu.com/p/04c03059e538

点赞 评论 复制链接分享
• 默默悟问 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;
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]

你假定的结果不正确。
``````
点赞 评论 复制链接分享
• 以伽利略之名 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) //奇偶分裂，奇偶数列都是连续不相邻的
{
}
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)
{
string line = Console.ReadLine();
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";

}

点赞 评论 复制链接分享
• 精锐小菜鸡 2018-04-23 03:23
`````` 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;
}
``````
点赞 评论 复制链接分享
• 默默悟问 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;
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;
}

点赞 评论 复制链接分享
• 精锐小菜鸡 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(",");
}

``````
点赞 评论 复制链接分享