Sum of Variable Length Subarrays
Source: leetcode
Difficulty: Easy
Tags: array, prefix-sum

You are given an integer array `nums` of size `n`. For **each** index `i` where `0 <= i < n`, define a subarray `nums[start ... i]` where `start = max(0, i - nums[i])`.


Return the total sum of all elements from the subarray defined for each index in the array.


 


**Example 1:**



**Input:** nums \= \[2,3,1]


**Output:** 11


**Explanation:**




| i | Subarray | Sum |
| --- | --- | --- |
| 0 | `nums[0] = [2]` | 2 |
| 1 | `nums[0 ... 1] = [2, 3]` | 5 |
| 2 | `nums[1 ... 2] = [3, 1]` | 4 |
| **Total Sum** |  | 11 |


The total sum is 11\. Hence, 11 is the output.



**Example 2:**



**Input:** nums \= \[3,1,1,2]


**Output:** 13


**Explanation:**




| i | Subarray | Sum |
| --- | --- | --- |
| 0 | `nums[0] = [3]` | 3 |
| 1 | `nums[0 ... 1] = [3, 1]` | 4 |
| 2 | `nums[1 ... 2] = [1, 1]` | 2 |
| 3 | `nums[1 ... 3] = [1, 1, 2]` | 4 |
| **Total Sum** |  | 13 |


The total sum is 13\. Hence, 13 is the output.



 


**Constraints:**


- `1 <= n == nums.length <= 100`
- `1 <= nums[i] <= 1000`




C++ solution:
class Solution {
public:
    int subarraySum(vector<int>& nums) {
        int total = 0;
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            int start = std::max(0, i - nums[i]);
            for (int j = start; j <= i; ++j) {
                total += nums[j];
            }
        }
        return total;
    }
};

Go solution:
func subarraySum(nums []int) int {
    total := 0
    n := len(nums)
    for i := 0; i < n; i++ {
        start := i - nums[i]
        if start < 0 {
            start = 0
        }
        sum := 0
        for j := start; j <= i; j++ {
            sum += nums[j]
        }
        total += sum
    }
    return total
}

Java solution:
class Solution {
    public int subarraySum(int[] nums) {
        int total = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int start = Math.max(0, i - nums[i]);
            for (int j = start; j <= i; j++) {
                total += nums[j];
            }
        }
        return total;
    }
}

JavaScript solution:
var subarraySum = function(nums) {
    let total = 0;
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        const start = Math.max(0, i - nums[i]);
        let sum = 0;
        for (let j = start; j <= i; j++) {
            sum += nums[j];
        }
        total += sum;
    }
    return total;
};

Python solution:
class Solution:
    def subarraySum(self, nums: List[int]) -> int:
        total = 0
        n = len(nums)
        for i in range(n):
            start = max(0, i - nums[i])
            for j in range(start, i + 1):
                total += nums[j]
        return total

Ruby solution:
def subarray_sum(nums)
  total = 0
  nums.each_index do |i|
    start = [0, i - nums[i]].max
    total += nums[start..i].sum
  end
  total
end