平时看到时会写写，但都没有总结过，以后写了就都放在这里了，看起来方便一些。
一、最大子序列和
注释：以下程序中 MaxSubSequenceSum()函数只是求出数组a的最大子序列和，函数MaxSubSequenceSum_Extend()除了求出最大子序列和之外，还记录了最大子序列的起始位置，放在_beg和_end变量中。
![[面试]找工作笔试面试过程中一些常考的写程序题](https://image.shishitao.com:8440/aHR0cHM6Ly93d3cuaXRkYWFuLmNvbS9pL2ZhYzY0ZjBiYjk3MGIwNTk2NjNiODVhOGI4MWEyM2MxMS5qcGc%3D.jpg?w=700&webp=1 "[面试]找工作笔试面试过程中一些常考的写程序题")
![[面试]找工作笔试面试过程中一些常考的写程序题](https://image.shishitao.com:8440/aHR0cHM6Ly93d3cuaXRkYWFuLmNvbS9pL2ZhYzY0ZjBiYjk3MGIwNTk2NjNiODVhOGI4MWEyM2MxMi5qcGc%3D.jpg?w=700&webp=1 "[面试]找工作笔试面试过程中一些常考的写程序题")
代码
#include < iostream >
using namespace std;
#define MIN_VALUE -1000000
int MaxSubSequenceSum( int a[], int n)
{
int sum = 0 ,maxvalue = MIN_VALUE;
for ( int i = 0 ;i < n; ++ i)
{
sum = sum + a[i];
if (sum > maxvalue)
maxvalue = sum;
if (sum < 0 )
sum = 0 ;
}
return maxvalue;
}
int MaxSubSequenceSum_Extend( int a[], int n, int & _beg, int & _end)
{
int sum = 0 ,maxvalue = MIN_VALUE;
int start = 0 ;
_beg = 0 ;
for ( int i = 0 ;i < n; ++ i)
{
sum = sum + a[i];
if (sum > maxvalue)
{
maxvalue = sum;
_beg = start;
_end = i;
}
if (sum < 0 )
{
sum = 0 ;
start = i + 1 ;
}
}
return maxvalue;
}
int main()
{
int a[] = { 4 , - 3 , 5 , - 2 , - 1 , 2 , 6 , - 2 };
int b[] = { - 1 , - 2 , - 3 , - 4 };
int c[] = { - 1 , 3 , - 4 , 4 , - 3 , 5 , - 2 , - 1 , 2 , 6 , - 2 };
int _beg,_end;
cout << MaxSubSequenceSum_Extend(a, sizeof (a) / sizeof ( int ),_beg,_end) << endl;
cout << " start from " << _beg << " to " << _end << endl;
cout << MaxSubSequenceSum_Extend(b, sizeof (b) / sizeof ( int ),_beg,_end) << endl;
cout << " start from " << _beg << " to " << _end << endl;
cout << MaxSubSequenceSum_Extend(c, sizeof (c) / sizeof ( int ),_beg,_end) << endl;
cout << " start from " << _beg << " to " << _end << endl;
return 0 ;
}
注：求二维数组的最大子数组和也可以通过类似的思路解决，具体方法可以参加编程之美2.15中详述，我只是在这里提一下，用降维的思路，二维数组如何才能降维到一维呢？如果从第i行到第j行是确定下来的，那么二维是不是就降成一维的了。
二、strcpy和strncpy函数的实现
注：求二维数组的最大子数组和也可以通过类似的思路解决，具体方法可以参加编程之美2.15中详述，我只是在这里提一下，用降维的思路，二维数组如何才能降维到一维呢？如果从第i行到第j行是确定下来的，那么二维是不是就降成一维的了。
二、strcpy和strncpy函数的实现
代码
// assert()函数在头文件assert.h中
#include < assert.h >
// 注意：strcpy实现过程中把strSrc字符串中最后一个NULL赋值到strDest中了
char * strcpy( char * strDest, const char * strSrc)
{
assert((strDest != NULL) && (strSrc != NULL));
char * strDestCopy = strDest;
while (( * strDest ++ = * strSrc ++ ) != NULL);
return strDestCopy;
}
// 注意：strncpy实现有不同的版本，主要看题目要求。
// 版本一：如果count小于strSrc的长度，那么在strDest结尾处是没有结束符NULL的，如果count大于strSrc长度，只复制strSrc到结束
char * strncpy( char * strDest, const char * strSrc,size_t count)
{
assert((strDest != NULL) && (strSrc != NULL));
char * strDestCopy = strDest;
while (count --&& ( * strDest ++ = * strSrc ++ ) != NULL);
return strDestCopy;
}
// 版本二：如果count小于strSrc的长度，那么在strDest结尾处是没有结束符NULL的，如果count大于strSrc长度，剩下空间在strDest中填充NULL
char * strncpy( char * strDest, const char * strSrc,size_t count)
{
assert((strDest != NULL) && (strSrc != NULL));
char * strDestCopy = strDest;
for (size_t i = 0 ;i < count; ++ i)
{
if (( * strDest ++ = * strSrc ++ ) == NULL)
{
while ( ++ i < count)
* strDest ++ = NULL;
return strDestCopy;
}
}
return strDestCopy;
}
貌似版本二是默认的实现版本，具体实现可以根据题目要求做相应的改变。
三、最长递增子序列
代码
#include
<
iostream
>
using
namespace
std;
//
最大递增子序列
//
Largest Incremental SubSequence(LIS)
//
返回数组a中的最大值
int
maxValue(
int
a[],
int
n)
{
int
max_value
=
a[
0
];
for
(
int
i
=
1
;i
<
n;
++
i)
if
(a[i]
>
max_value)
max_value
=
a[i];
return
max_value;
}
//
返回数组a中的最大递增子序列的长度
/*
其中temparray[i]代表以a[i]为最大元素的最长递增子序列的长度
很容易就可以想到有如下公式：
假设在目标数组a[]的前i个元素中，最长递增子序列的长度为temparray[i]。那么，
temparray[i+1]=max{1,temparray[k]+1},a[i+1]>a[k],for any k <= i
接下来程度的算法复杂度是O(N*N),属于比较基本的解法
*/
int
LIS(
int
a[],
int
n)
{
int
*
temparray
=
new
int
[n];
for
(
int
i
=
0
;i
<
n;
++
i)
{
temparray[i]
=
1
;
for
(
int
j
=
0
;j
<
i;
++
j)
if
(a[i]
>
a[j]
&&
temparray[j]
+
1
>
temparray[i])
temparray[i]
=
temparray[j]
+
1
;
}
return
maxValue(temparray,n);
}
//
动态规划的方法求解待添加
int
LIS_DP(
int
a[],
int
n)
{
}
int
main()
{
int
a[]
=
{
1
,
-
1
,
2
,
-
3
,
4
,
-
5
,
6
,
-
7
};
cout
<<
LIS(a,
sizeof
(a)
/
sizeof
(
int
))
<<
endl;
return
0
;
}