74-计算所有奇数子数组的和(C语言)

墨蓝 2022-12-27 07:30 120阅读 0赞

给你一个正整数数组 arr ，请你计算所有可能的奇数长度子数组的和。

子数组 定义为原数组中的一个连续子序列。  
请你返回 arr 中 所有奇数长度子数组的和 。

示例 1：  
输入：arr = \[1,4,2,5,3\]  
输出：58  
解释：所有奇数长度子数组和它们的和为：  
\[1\] = 1  
\[4\] = 4  
\[2\] = 2  
\[5\] = 5  
\[3\] = 3  
\[1,4,2\] = 7  
\[4,2,5\] = 11  
\[2,5,3\] = 10  
\[1,4,2,5,3\] = 15  
我们将所有值求和得到 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58

示例 2：  
输入：arr = \[1,2\]  
输出：3  
解释：总共只有 2 个长度为奇数的子数组，\[1\] 和 \[2\]。它们的和为 3 。

示例 3：  
输入：arr = \[10,11,12\]  
输出：66

提示：  
1 <= arr.length <= 100  
1 <= arr\[i\] <= 1000

#include<stdio.h>
    int Sumarr(int* arr, int len)
    {
        
        int res = 0;
        for (int i = 0; i < len; i++) //从头开始遍历
    	{
        
            for (int j = 1; j <=len- i ; j += 2) 
            //当前情况下的1,3,5..长度类型的子数组
    		{
        
                for (int m = i; m < i + j; m++)//输出当前的子数组的值
    			{
        
                    res = res + arr[m];//累加值
                }
            }
        }
        return res;//返回最后累加后的值
    }
    
    int main()
    {
        
    	int arr[]={
        10,11,12};
    	printf("%d\n",Sumarr(arr,sizeof(arr)/sizeof(arr[0])));
    	return 0;
    }

运行截图如下  
![在这里插入图片描述][202012081938214.png_pic_center]  
此方法时间复杂度较大。

[202012081938214.png_pic_center]: /images/20221120/5c794f97a3214d51af2b66cdb358672e.png