算法第三张实践报告

本文主要是介绍算法第三张实践报告，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1 问题分析

1.1 问题概述

给定一段序列，子段和为其中一段子序列相加所得的和数，求最大子段和数。

1.2 算法实现

根据动态规划方程 dp[i] = max(dp[i - 1], k);

其中 k 表示从0到 i 的相加的和大于0的子段，若 k 小于0则令 k 等于当前位置的数值，并且重新计算子段和。

1.3 实际问题

给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时，定义子段和为0。

要求算法的时间复杂度为O(n)。

输入格式:

输入有两行：

第一行是n值（1<=n<=10000)；

第二行是n个整数。

输出格式:

输出最大子段和。

输入样例:

6
-2 11 -4 13 -5 -2

输出样例:

20

1.4 代码实现

#include <iostream>
using namespace std;
int main(){
    int n, temp[10005], dp[10005], flag = 0, k;
    cin >> n;  
    for(int i = 1; i <= n; i++)
    {
        cin >> temp[i];
         if(temp[i] >= 0) flag = 1;    //只要有一个数大于0，让标志为1 
     }
    //dp[i]是1~i中最大子段和
    //k: k从0到i加和大于0的子段和，遇到子段小于0的扔掉重新开始计长度
     for(int i = 1; i <= n; i++)
    {
        if(k>0) k += temp[i];
         else k = temp[i];        
         dp[i] = max(dp[i-1], k);    
     }
    if(flag == 0) cout << 0;    //如果全为负数，则输出0 
    else cout << dp[n];
    return 0;
} 

1.5 时间复杂度及空间复杂度

1.5.1 时间复杂度

算法中用一个for循环遍历了temp数组，故时间复杂度为 T(n) = O (n)

1.5.2 空间复杂度

算法中只开辟了一个辅助数组dp[n]，故空间复杂度为O(n)

1.6 心得体会

本次上机一开始理解错了意思，一直想像之前那样用二分法求解，但写出来后听到其他组同学与老师交流才发现，要用到书里的动态规划方程去书写。再回到宿舍后，通过理解其他同学的代码思路，我终于搞明白了要求和具体实现方法。

2 对动态规划算法的理解和体会

动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推的方式去解决。

1 拆分问题

根据问题的可能性把问题划分成一步一步这样就可以通过递推或者递归来实现。如果只有一种情况时，先推出最佳的选择应该怎么做，再根据这个最佳选择往前一步推导，得到前一步的最佳选择，以此类推。

2 定义问题状态和状态之间的关系
将前面拆分的步骤之间的关系，用一种量化的形式表现出来，类似于高中学的推导公式，也就是动态规划转移方程式。

3 保留最优解
找到最优解，并把最优解保存下来，舍弃所有较差解释，这样大大降低了时间复杂度。

这篇关于算法第三张实践报告的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！