算法课老师布置的一道简单题目,大家笑一笑就好、
1.对于以下几个矩阵应用算法matchain.
$M_1$ : $2\times 3$ , $M_2$: $3\times6$, $M_3$:$6\times4$, $M_4$ : $4\times2$, $M_5$:$2\times7$
(a)找出这5个矩阵相乘需要的最小乘法数量。
(b)请给一个括号表达式,使在这种次序下达到的乘法次数最少
-------------待完成----------------------------------------
1.抄题:对给定数组A,其长度为n,找出数组A中的最大非空子数组,例如A={13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7},最大和子数组是{18,20,-7,12}.
输出:最大子数组和18,20,-7,12以及子数组的和43.
2.算法思想:动态规划,从最后一个dp[i]开始考虑,只有由两种状态转移过来,加入上一个dp[i-1](表示i-1的和子数组),或者不要i-1的和,最后加上a[i]。
3.程序代码:如下
4.程序运行结果
5.分析算法复杂度:时间复杂度:O(n)
空间复杂度:T(n)
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10010;
int a[N] = {13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7};
int dp[N];
int main()
{
int n = 16;
int res = 0;
dp[0] = a[0];
for(int i=1;i<n;i++)
{
dp[i] = a[i]+max(0,dp[i-1]);
res = max(res,dp[i]);
}
int index = 0, num = 0, res2 = res ;
int ans[N];
for(int i=1;i<n;i++)
{
if(dp[i]==res)
{
index = i;
break;
}
}
while(res2 > 0)
{
res2 -= a[index];
index--;
num++;
}
cout<<"最大子数组 ";
for(int i=index+1;i<index+1+num;i++)
cout<<a[i]<<' ';
cout<<"以及子数组和 "<<res;
}