首页 > 试题广场 >

数组单调和

[编程题]数组单调和
  • 热度指数：13365 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

现定义数组单调和为所有元素i的f(i)值之和。这里的f(i)函数定义为元素i左边(不包括其自身)小于等于它的数字之和。请设计一个高效算法，计算数组的单调和。

给定一个数组A同时给定数组的大小n，请返回数组的单调和。保证数组大小小于等于500，同时保证单调和不会超过int范围。

测试样例： 
[1,3,5,2,4,6],6
返回：27
算法知识视频讲解
添加回答
Python
诸葛小愚头像 诸葛小愚 
# -*- coding:utf-8 -*-

class MonoSum:
    def calcMonoSum(self, A, n):
        # write code here
           #[1,3,5,2,4,6],6
        #1+4+1+6+15=27
        if n==1:
            return 0
        r=0
        for i in range(n):
            for j in range(i):
                if A[j]<=A[i]:
                    r+=A[j]
        return r

发表于 2018-08-09 22:31:08 回复(0)
Python
离疏头像 离疏 
# -*- coding:utf-8 -*-
class MonoSum:
    def calcMonoSum(self, A, n):#动态规划
        ans=0
        if n<=1:
            return 0
        else:
            for i in range(n-1):#f(i)等于f(i-1)加上元素i左边小于等于它的数字之和
                if A[i]<=A[n-1]:
                    ans+=A[i]
            return ans+self.calcMonoSum(A,n-1)#递归调用计算f(i-1)

发表于 2018-07-31 14:47:32 回复(0)
Python
serendipity_T头像 serendipity_T 
从前往后遍历，先把前面的i个数按小到大排序，第i+1个到了以后插入第i+1个  
使前i+1个从小到大排序，然后把前插入之后的的位置K前面的K-1个sum起来就好了。
def sort(data,i):     temp = data[i]     i = i-1     while i>=0 and temp<data[i]:         data[i+1] = data[i]         i-=1     data[i+1] = temp     return sum(data[:i+1])



def ojbk(data):     count =0     m = len(data)     for i in range(1,m):         count += sort(data,i)     print(count)
编辑于 2018-05-19 11:46:21 回复(0)
Python
华科平凡头像 华科平凡

python一行 

def calcMonoSum(self, A, n):
        return sum(map(lambda i: sum(filter(lambda c: c <= A[i], A[:i])), range(1, n)))


编辑于 2019-10-06 21:19:18 回复(2)
Python
改个名字解解毒...头像 改个名字解解毒... 
#!/usr/bin/env python
#-*- coding:utf8 -*-
# -*- coding:utf-8 -*-

class MonoSum:
    def calcMonoSum(self, A, n):
        # write code here
        nums = [0 for i in range(n)]
        for i in range(1,n):
            for j in range(i):
                if A[i] >= A[j]:
                    nums[i] += A[j]
        return sum(nums)

发表于 2017-08-08 10:32:43 回复(0)
Python
牛客1841689号头像 牛客1841689号
import sys

def calcMonoSum(A,n):
    if n > 500:
        print("n should be no greater than 500")
        return
    subsumList = []
    for i in range(len(A)-1,0,-1):
        subsum = 0
        for j in range(0,i):
            if A[j] <= A[i]:
                subsum += A[j]
        subsumList.append(subsum)
    cms = sum(subsumList)
    if cms < sys.maxsize:
        print(cms)
    else:
        print("Overflow...")
        return

A, n = (1,3,5,2,4,6), 6
calcMonoSum(A,n)
发表于 2016-09-10 11:14:20 回复(0)
Python
异乡异客头像 异乡异客 
class MonoSum:
    def calcMonoSum(self, A, n):
        # write code here
        num=0
        for i in range(1,n):
            for j in range(0,i):
                if A[j]<=A[i]:
                    num=num+A[j]
        return num

发表于 2016-06-16 23:06:24 回复(0)
Python
XK15601598155头像 XK15601598155
# -*- coding:utf-8 -*-

class MonoSum:
    def calcMonoSum(self, A, n):
        # write code here
        arg = []
        for i in range(n):
            for k in range(i):
                if A[k] <= A[i]:
                    arg.append
            return sum(arg)

发表于 2016-06-13 17:10:51 回复(0)
提交观点

问题信息

动态规划 查找
来自：经典算法题精讲（六）-...
难度：
8条回答 28454浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号