[leetCode] 1588. Sum of All Odd Length Subarrays (Python)

Given an array of positive integers arr, calculate the sum of all possible odd-length subarrays.

A subarray is a contiguous subsequence of the array.

Return the sum of all odd-length subarrays of arr.

 

Example 1:

Input: arr = [1,4,2,5,3]
Output: 58
Explanation: The odd-length subarrays of arr and their sums are:
[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
If we add all these together we get 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58

Example 2:

Input: arr = [1,2]
Output: 3
Explanation: There are only 2 subarrays of odd length, [1] and [2]. Their sum is 3.

Example 3:

Input: arr = [10,11,12]
Output: 66

Constraints:

• 1 <= arr.length <= 100
• 1 <= arr[i] <= 1000

Solution

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        max_len = len(arr)
        
        arr_len = len(arr)
                
        if max_len % 2 == 0:
            max_len = max_len - 1
        
        answer_list = []
        
        for i in range(1, max_len+1, 2):
            for j in range(arr_len - i + 1):
                answer_list.append(sum(arr[j:j+i]))              
        
        return sum(answer_list)

Solution 해설

이 문제는 홀수 길이의 subarray를 모두 구하고 해당 subarray들을 모두 합한 값을 구하는 문제입니다.

 

먼저 홀수 길이의 subarray의 최대 길이가 몇인지 확인하기위해서 입력 받은 리스트의 길이를 활용하여 구합니다.

입력 받은 리스트의 길이가 짝수이면 1을 뺀 숫자가 최대의 길이

입력 받은 리스트이 길이가 홀수이면 해당 길이가 최대의 길이가 됩니다.

 

그 다음 이중 for문을 활용하여 각 홀수 길이의 subarray를 구하고

그 subarray의 합을 리스트에 저장해 두었다가 마지막으로 해당 리스트의 합을 return 합니다.

SOMJANG/CODINGTEST_PRACTICE