目录
- 前言
- 思路梳理
- 题解最优思路
- 我的思路
- 思路一 考虑连续 对一半 ×
- 思路二 基于思路一的优化 ×
- 思路三 基于思路二的优化 √ 通过了但是效率太低
- 我的代码
前言
今天继续做动态dp的第三题，最大子序和，昨天做最大连续子数组的和已经有一些写状态转移方程的经验了，今天自己想了一个思路一。
思路梳理
题解最优思路
写到这里我想惊叹一下数学语言的魅力，因为我虽然想清楚了但是却表达不清楚。一个数学公式代替了我的一大坨废话。
这里最大的坑在于，状态转移的前一个状态需要满足两个条件。从我自己的思路三优化到这里也并不复杂，感觉我自己的思路就好像是先把水煮开再一起下饺子，官方思路是冷水的时候我就可以把饺子放下去慢慢煮了。很多判断可以在遍历的时候就做了。
以下是代码：
int max_subArr_Ascending_order_optimize_Original(vector<int> Arr) {
vector<int> resArr(Arr.size());
for (int i = 0; i < Arr.size(); i++) {
//先把最差的情况确定好，最差的情况也不过就是1了
resArr[i] = 1;
//然后再循环左边比它小的最大值
for (int j = 0; j < i; j++) {
if (Arr[j] < Arr[i]) {
resArr[i] = max(resArr[j] + 1, resArr[i]);
}
}
}
return *max_element(resArr.begin(),resArr.end());
}
我的思路
思路一 考虑连续 对一半 ×
跟昨天的类似，也是以子数组的最后一个元素的位置作为标记。首先我找到最大的连续升数组，然后再在这个基础上加上前面的不连续的。但是很遗憾，这个思路只通过了一半的测试用例，想想看确实是有很大问题的。不应该考虑连续，连续的bug太大了。
class Solution {
public:
int lengthOfLIS(vector<int>& Arr) {
int res = 1;
vector<int> resArr(Arr.size());
resArr[0] = 1;
int left_max_location;
for (int i = 1; i < Arr.size(); i++) {
// 首先找到左边比它小，且最大的元素
left_max_location = search_left_less_than(i, Arr, resArr);
if (left_max_location == -1) {
resArr[i] = 1;
} else {
resArr[i] = left_max_location + 1;
}
if (resArr[i] >= res) {
res = resArr[i];
}
}
return res;
}
int search_left_less_than(int i, vector<int>& Arr, vector<int>& resArr) {
// 如果这个元素比前面的所有元素都小的话，就返回-1
if (*min_element(Arr.begin(), Arr.begin() + i) >= Arr[i]) {
return -1;
}
// 重新设置一个数组，把所有值比i元素小的都存进去。
vector<int> left_less(i);
for (int j = i - 1; j >= 0; j--) {
if (Arr[j] < Arr[i]) {
left_less.push_back(resArr[j]);
}
}
// 存好了之后我现在就找一个最大值了
int left_location_max =
*max_element(left_less.begin(), left_less.end());
// 直接把这个最大值给返回出去
return left_location_max;
}
};
思路二 基于思路一的优化 ×
思路二我继续来考虑怎么去设置这个状态转移方程，以i位置结束的连续递增数组，它和次长的递增数组没有 物理空间 上 紧挨着的 特征了。因此我觉得它应该考虑的是 数组左边 第一个比它小的元素值，在它的基础上＋1。如此我们可以得到一下总结：
- 我们给最大子数组设置标签：子数组在i元素处结尾，设置一个resArr来存储以这个结尾的最大递增长度。
- 考虑初始条件：resArr[0]初始化为1；
- 状态转移方程：
resArr[i]等于resArr[j]+1( j 为 i 的左边第一个小于自己本身元素的位置） 如果这个元素是从0到i最大的，就直接令resArr=1；
这个思路也是错的，并不是数组左边第一个值比它小的元素，而是需要满足①比它小 ②以这个位置结束的递增子数组的长度值要是最大的
思路三 基于思路二的优化 √ 通过了但是效率太低
修改了之后，发现我的解答还是错误，一行行debug发现是我的函数用的有问题：
vector函数自己有丰富的方法，可以直接帮我们找到数组里面的最大值，方法是
max_element（要引入algorithm库），但是它其实有点类似于python的切片，函数的参数要给出vecotor的迭代器（Arr.begin(),Arr.end()）,我的错误就在于这个函数他的索引对象是从参数一开始到参数二的前一个，（Arr.end()其实就是指向vector最后一个参数的下一个）。
修改之后，测试都通过了，但是超出内存限制了。
这个其实是因为我在传递函数的时候没有使用引用，没使用引用就会在调用的时候复制一遍占用大量内存。
改完之后，终于通过了。。。但是依旧感觉好菜哈哈哈哈。
class Solution {
public:
int lengthOfLIS(vector<int>& Arr) {
int res = 1;
vector<int> resArr(Arr.size());
resArr[0] = 1;
int locate = 0;
int left_max_location;
for (int i = 1; i < Arr.size(); i++) {
//首先找到左边比它小，且最大的元素
left_max_location = search_left_less_than(i, Arr, resArr);
if (left_max_location == -1) {
resArr[i] = 1;
}
else {
resArr[i] = left_max_location + 1;
}
if (resArr[i] >= res) {
res = resArr[i];
locate = i;
}
}
return res;
}
int search_left_less_than(int i, vector<int> &Arr, vector<int> &resArr) {
//如果这个元素比前面的所有元素都小的话，就返回-1
if (*min_element(Arr.begin(), Arr.begin() + i ) >= Arr[i]) {
return -1;
}
vector<int> x = resArr;
//重新设置一个数组，把所有值比i元素小的都存进去。
vector<int> left_less(i, 0);
for (int j = i - 1; j >= 0; j--) {
if (Arr[j] < Arr[i]) {
left_less[j] = resArr[j];
}
}
//存好了之后我现在就找一个最大值了
int left_location_max = *max_element(left_less.begin(), left_less.end());
//直接把这个最大值给返回出去
return left_location_max;
}
};
我的代码
#include<iostream>
#include<vector>
#include <algorithm>
using namespace std;
class solution {
public:
//int max_subArr_sum(vector<int> Arr) {
// int res = Arr[0];
// vector<int> resArr(Arr.size());
// resArr[0] = res;
// for (int i = 1; i < Arr.size(); i++) {
// /*if (resArr[i - 1] + Arr[i] > resArr[i - 1]) {
// resArr[i] = resArr[i - 1] + Arr[i];
// }
// else {
// resArr[i] = resArr[i - 1];
// }
// if (resArr[i] > res) {
// res = resArr[i];
// }*/
// if (resArr[i - 1] > 0) {
// resArr[i] = resArr[i - 1] + Arr[i];
// }
// else {
// resArr[i] = Arr[i];
// }
// if (resArr[i] > res) {
// res = resArr[i];
// }
// }
// return res;
//}
//int max_subArr_Ascending_order(vector<int> Arr) {
// int res = 1;
// vector<int> resArr(Arr.size());
// resArr[0] = 1;
// int locate = 0;
// for (int i = 1; i < Arr.size(); i++) {
// if (Arr[i - 1] >= Arr[i]) {
// resArr[i] = 1;
// }
// else {
// resArr[i] = resArr[i - 1] + 1;
// }
// if (resArr[i] >= res) {
// res = resArr[i];
// locate = i;
// }
// }
// int current_max = Arr[locate - resArr[locate] + 1];
// for (int i = locate - 1; i >= 0; i--) {
// if (Arr[i] < current_max) {
// res++;
// current_max = Arr[i];
// }
// }
// return res;
//}
int max_subArr_Ascending_order_optimize(vector<int> Arr) {
int res = 1;
vector<int> resArr(Arr.size());
resArr[0] = 1;
int left_max_location;
for (int i = 1; i < Arr.size(); i++) {
//首先找到左边比它小，且最大的元素
left_max_location = search_left_less_than(i, Arr, resArr);
if (left_max_location == -1) {
resArr[i] = 1;
}
else {
resArr[i] = left_max_location + 1;
}
if (resArr[i] >= res) {
res = resArr[i];
}
}
return res;
}
int search_left_less_than(int i, vector<int> &Arr, vector<int> &resArr) {
//如果这个元素比前面的所有元素都小的话，就返回-1
if (*min_element(Arr.begin(), Arr.begin() + i ) >= Arr[i]) {
return -1;
}
//重新设置一个数组，把所有值比i元素小的都存进去。
vector<int> left_less(i);
for (int j = i - 1; j >= 0; j--) {
if (Arr[j] < Arr[i]) {
left_less.push_back(resArr[j]);
}
}
//存好了之后我现在就找一个最大值了
int left_location_max = *max_element(left_less.begin(), left_less.end());
//直接把这个最大值给返回出去
return left_location_max;
}
int max_subArr_Ascending_order_optimize_Original(vector<int> Arr) {
vector<int> resArr(Arr.size());
for (int i = 0; i < Arr.size(); i++) {
//先把最差的情况确定好，最差的情况也不过就是1了
resArr[i] = 1;
//然后再循环左边比它小的最大值
for (int j = 0; j < i; j++) {
if (Arr[j] < Arr[i]) {
resArr[i] = max(resArr[j] + 1, resArr[i]);
}
}
}
return *max_element(resArr.begin(),resArr.end());
}
};
int main() {
solution s;
vector<int> Arr = { 3,1,2 };
int x = s.max_subArr_Ascending_order_optimize(Arr);
cout << x << endl;
}
