# Running Sum of 1d Array

###### tags: `Easy`
> [name=出題者 : 曾致銘]

## Problem
給定一個整數 `length` 和一個長度為 `length` 的整數陣列 `nums`。我們定義一個數字陣列的「動態和」為滿足 `runningSum[i] = nums[0] + nums[1] + ... + nums[i]`。請回傳 `nums` 的動態和。

### Examples
範例 1：

輸入: 4 1 2 3 4
輸出: 1 3 6 10
解釋: 動態和計算過程為 1, 1+2, 1+2+3, 1+2+3+4

範例 2：

輸入: 5 1 1 1 1 1
輸出: 1 2 3 4 5
解釋: 動態和計算過程為 1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1

範例 3：

輸入: 5 3 1 2 10 1
輸出: 3 4 6 16 17
解釋: 動態和計算過程為 3, 3+1, 3+1+2, 3+1+2+10, 3+1+2+10+1

### Constraints
- $1 \le$ `length` $\le 1000$
- $-10^6 \le$ `nums[i]` $\le 10^6$

### Hints
:::spoiler Hint 1
請思考要如何通過前一個動態和來計算當前的動態和 ?
:::

## Solution
:::spoiler Description
### Approach 1: 創建另一陣列作為輸出

#### 思路
我們需要算出 `nums[i]` 的動態和，其中 `i` 為從 `0` 到 `length - 1` 的整數且 `length` 是該陣列的長度。計算方法即為 `nums[0]` 到 `nums[i]` 的全項總和。我們可以創建一個相同長度的陣列作為輸出，並從第 `0` 項開始計算。在這種情況下，對於第 `i` 項元素，我們皆已經計算出其前一項的動態和，即 `nums[0]` 到 `nums[i - 1]` 的全項總和。因此，與其每一項都從頭開始計算其動態和，不如直接把該項加上已算好的前一項的動態和來的快速。

#### 算法
1. 創建一長度為 `length` 的陣列 `result`。
2. 把 `result[0]` 的值設為 `nums[0]` 的值。
3. 把 `result[i]` 的值設為 `nums[i] + result[i-1]` 的值。
4. 重複步驟 3 直至 `i` 到達 `length-1`。

// 以下省略 cin 與 cout，僅呈現演算法部分
// 步驟 1
int result[length];
// 步驟 2
result[0] = nums[0];

for (int i = 1; i < length; i++) {
    // 步驟 3
    result[i] = result[i - 1] + nums[i];
}

#### 複雜度分析
- 時間複雜度: $O(n)$ 其中 $n$ 為輸入陣列的長度。這是由於我們使用了一個遍歷輸入陣列的迴圈所致。
- 空間複雜度: $O(1)$ 因為我們並沒有使用額外空間來「計算」。*註：作為輸出和輸入的空間不納入計算空間複雜度的考量。*

### Approach 2: 把輸入陣列當作輸出使用

#### 思路
在上一個層級中我們額外創建了一個陣列作為輸出。然而其實不用。我們可以對輸入陣列做一模一樣的計算且獲得相同的結果。

#### 算法
1. 把 `nums[i]` 加上 `i-1` 項的動態和，而 `i-1` 項的動態和即被存在 `nums[i-1]`。
2. 重複步驟 1 直至 `i` 到達 `length-1`。

// 以下省略 cin 與 cout，僅呈現演算法部分
for (int i = 1; i < length; i++) {
    // 步驟 1
    nums[i] += nums[i - 1];
}

#### 複雜度分析
- 時間複雜度: $O(n)$ 其中 $n$ 為輸入陣列的長度。
- 空間複雜度: $O(1)$ 因為我們並沒有使用額外空間來「計算」。*註：作為輸出和輸入的空間不納入計算空間複雜度的考量。*

### 完整解答

#include <iostream>
using namespace std;

int main() {
    int length;
    cin >> length;
    int nums[length];
    
    for (int i = 0; i < length; i++) {
        cin >> nums[i];
        if (i > 0) {
            nums[i] += nums[i - 1];
        }
    }
    
    for (auto num : nums) {
        cout << num << " ";
    }
    
    cout << endl;
}

:::

## Reference
https://leetcode.com/problems/running-sum-of-1d-array/