# [Codewars] Maximum subarray sum

###### tags: `解題筆記`

## 練習資訊

等級：5 kyu
題目：[Maximum subarray sum](https://www.codewars.com/kata/54521e9ec8e60bc4de000d6c/javascript)
練習時間：

- 2023/03/26（要再練習一次，題目要看清楚！）
- 2023/04/16（還是有一點卡卡的，需要再練習一次）
- 2023/06/14（還是要再練習一次，題目要看清楚！）

## 題目說明

### 中文

給一陣列，必須計算出該陣列連續值最大的和數是多少，比如說：

maxSequence([-2, 1, -3, 4, -1, 2, 1, -5, 4])
// should be 6: [4, -1, 2, 1] -> 因為 [4 + -1 + 2 + 1] 是該陣列連續值最大的和數

如果陣列都是正數，那麼連續值最大的和數就是陣列中全部的值相加；如果陣列都是負數，那麼就給 0；如果是空陣列就回傳 0。

### 英文

The maximum sum subarray problem consists in finding the maximum sum of a contiguous subsequence in an array or list of integers:

maxSequence([-2, 1, -3, 4, -1, 2, 1, -5, 4])
// should be 6: [4, -1, 2, 1]

Easy case is when the list is made up of only positive numbers and the maximum sum is the sum of the whole array. If the list is made up of only negative numbers, return 0 instead.

Empty list is considered to have zero greatest sum. Note that the empty list or array is also a valid sublist/subarray.

## 我的方法

### 思路

1. 因為是「連續值」，所以跑一層迭代就可以
2. 只要是負數就直接給 0
3. 為了要知道值的和數，所以必須讓值相加
- 但是為了要避免相加後是正數且比上次迭代小的情況，必須開兩個變數保存，一個保存答案，另一個保存當前計算的和數

const arr = [4, -1, 2, 1, -5, 4]
/* 比方來說這種情況，如果沒有阻擋的話就會變成
 * 4
 * 3 -> 4 - 1
 * 5 -> 5 + 2
 * 6 -> 5 + 1
 * 1 -> 6 - 1 （這裡出現問題！）
 * 5
 * / 

結果一開始寫的是：

var maxSequence = function(arr){
  let x = 0;

  for (let i = 0; i < arr.length; i++) {
    const temp = x + arr[i]
    
    if (temp > 0) {
      x = temp
    }
  }
  
  return x
}

結果都可以過一開始的測試，但是 random test 就是過不了。

思考了很久，就偷翻之前第一次的解答後實作：

var maxSequence = function(arr){
  let x = 0; // 保存當次迭代的記錄
  let y = 0; // 保存答案
  
  for (let i = 0; i < arr.length; i++) {
    x += arr[i]
    
    // 如果 < 0 就代表是負數，直接丟 0
    // 反之就繼續拿上次記錄 + 這次迭代的值計算答案
    if (x < 0) {
      x = 0
    }
    
    // 比對當前的記錄是否是答案
    // 避免迭代的記錄是正數，不過 < 答案
    if (y < x) {
      y = x
    }
  }
  
  return y
}

## 厲害的解答

### 思路

1. 透過 `Array.reduce()` 迭代陣列，取得當前的值計算（`accumulator` -> 第一次迭代如有預設值就是預設值，反之為陣列第一位，之後第二次迭代就是該次迭代回傳的值，`currentValue` -> 第一次迭代如有預設值就是陣列第一位，反之就是第二位，之後就是按照順序的值）
2. `Math.max()` 會取最大的數
3. 透過 functional scope 往外找的特性，會取得上次迭代的值（也就是和數）

:::spoiler

var maxSequence = function(arr){
    var currentSum = 0; // 記錄迭代計算
    return arr.reduce(function(maxSum, number){
        currentSum = Math.max(currentSum+number, 0); // 是負數就給 0，代表不是連續
        return Math.max(currentSum, maxSum);
    }, 0);
}

:::