首页 > 代码库 > 数组单调和
数组单调和
时间限制:3秒 空间限制:32768K 热度指数:7374
本题知识点: 查找 动态规划
题目描述
现定义数组单调和为所有元素i的f(i)值之和。这里的f(i)函数定义为元素i左边(不包括其自身)小于等于它的数字之和。请设计一个高效算法,计算数组的单调和。
给定一个数组A同时给定数组的大小n,请返回数组的单调和。保证数组大小小于等于500,同时保证单调和不会超过int范围。
测试样例:
[1,3,5,2,4,6],6
返回:27
1 class MonoSum { 2 public: 3 int calcMonoSum(vector<int> A, int n) { 4 // write code here 5 int sum = 0; 6 for(int i=1; i<n; i++) 7 { 8 int fi = 0; 9 for(int j=0; j<i; j++) 10 if(A[j]<=A[i]) 11 fi+= A[j]; 12 sum += fi; 13 } 14 return sum; 15 } 16 };
数组单调和
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。