Author: Claire Chang

function maxSubarray(nums) {
  if (!nums || nums.length === 0) {
    return 0;
  }
  let maxSum = nums[0];
  let curSum = nums[0];
  for (let i = 1; i < nums.length; i++) {
    curSum = Math.max(nums[i], curSum + nums[i]);//要不要包含前面的
    maxSum = Math.max(maxSum, curSum);//要不要包含自己
  }
  return maxSum;
}

function solution(A) {
    if(A.length <= 1){
        return 0
    }
    var diff = []
    var current_diff = 0
    for (var i = 1; i < A.length; i++) {
        current_diff = A[i] - A[i - 1]
        diff.push(current_diff)
    }
    var max_sum = diff[0]
    var curr_sum = diff[0]
    for (var i = 1; i < diff.length; i++) {
        curr_sum = Math.max(diff[i], curr_sum + diff[i]);
        max_sum = Math.max(curr_sum, max_sum);
    }
    return max_sum < 0 ? 0:max_sum
}

function solution(A) {
    if(A.length == 0) return 0
    var cur_sum = A[0]
    var max_sum = A[0]
    for(var i=1;i<A.length;i++){
        cur_sum = Math.max(A[i], cur_sum+A[i])
        max_sum = Math.max(max_sum, cur_sum)
    }
    return max_sum
}

function solution(A) {
    var candidate = 0
    var count = 0
    for(var i=0;i<A.length;i++){
        if(count == 0){
            candidate = A[i]
            count++
        }else if(candidate == A[i]){
            count++
        }else {
            count--
        }
    }
    var idx = []
    for(var i=0;i<A.length;i++){
        if(A[i] == candidate){
            idx.push(i)
        }
    }
    //console.log(idx)
    return idx.length > A.length/2 ? idx[0]:-1
}

function solution(A) {
    var candidate = 0
    var count = 0
    for(var i=0;i<A.length;i++){
        if(count == 0){
            candidate = A[i]
            count++
        }else if(candidate == A[i]){
            count++
        }else {
            count--
        }
    }
    var amount_list = []
    var currentCount = 0
    for(var i=0;i<A.length;i++){
        if(A[i] == candidate){
            currentCount++
        }
        amount_list.push(currentCount)
    }
    var equi_leaders = 0
    for(var i=0;i<amount_list.length;i++){
        if(amount_list[amount_list.length-1]-amount_list[i] > (amount_list.length-i-1)/2 && amount_list[i] > (i+1)/2){
            equi_leaders++
        }
    }
    return equi_leaders
}

function solution(H) {
    var stack = []
    var total = 0
    for(var i = 0;i<H.length;i++){
        if(stack.length == 0){
            stack.push(H[i])
            total++
        }else if(i > 0 && H[i-1] > H[i]){
            var height = H[i-1]
            while(stack.length > 0){
                height = height - stack.pop()
                if(height < H[i]) {
                    total++
                    stack.push(H[i]-height)
                    break
                }else if(height == H[i]){
                    break
                }
            }
        }else if(i > 0 && H[i-1] < H[i]){
            stack.push(H[i]-H[i-1])
            total++
        }else if(i ==  0 && H[i-1] < H[i]){
            stack.push(H[i])
            total++
        }
        //console.log(i,stack, total)
    }
    return total
}

function solution(A, B) {
    var point = 0
    while(point < B.length){
        var currnet_direction = B[point]
        if(currnet_direction == 0){//往上
            while(point > 0 && A[point-1] < A[point]){
                //吃掉目標
                A.splice(point,1)
                B.splice(point,1)
            }
            //換目標
            point++
        }else{//往下
            while(point < B.length-1 && A[point+1] < A[point]){
                //吃掉目標
                A.splice(point+1,1)
                B.splice(point+1,1)
            }
            //換目標
            point++
        }
    }
    return A.length
}

function solution(A, B) {
    var alive_A = []
    var alive_B = []
    // 往下
    while(A.length > 0){
        var target = A.shift()
        var target_direction = B.shift()
        while(target_direction == 1 && B[0] == 0 && target > A[0]){
            A.shift()
            B.shift()
        }
        alive_A.push(target)
        alive_B.push(target_direction)
    }
    A = alive_A
    B = alive_B
    alive_A = []
    alive_B = []
    //往上
    while(A.length > 0){
        var target = A.pop()
        var target_direction = B.pop()
        while(target_direction == 0 && B[B.length-1] == 1 && target > A[A.length-1]){
            A.pop()
            B.pop()
        }
        alive_A.push(target)
        alive_B.push(target_direction)
    }
    return alive_A.length
}

function solution(A, B) {
    var point = 0
    var finish = 0
    while(A.length > 0){
        if(point >= A.length ){
            point = A.length-1
        }
        //console.log("main", A, B, point)
        if(point == 0 && B[point] == 0){
            finish ++
            A.shift()
            B.shift()
        }else if(point == A.length-1 && B[A.length-1] == 1){
            finish ++
            A.pop()
            B.pop()
        }else{
            var target_direction = B[point] == 0 ? -1:1
            while(A[point] > A[point+target_direction] && B[point] != B[point+target_direction]){
                A.splice(point+target_direction,1)
                B.splice(point+target_direction,1)
            }
            point = point+target_direction
        }
    }
    return finish
}

function solution(A, B) {
    var alive = 0
    var downstream = []
    for (var i = 0; i < A.length; i++) {
        if (B[i] == 1) {
            downstream.push(A[i])
        } else {
            //開始吃掉之前的往下的魚直到自己被吃掉
            while (downstream.length > 0 && downstream[downstream.length - 1] < A[i]) {
                downstream.pop()
            }
            if(downstream.length == 0){
                //過關
                alive++
            }
        }
    }
    return alive + downstream.length
}

function solution(S) {
    var data = S.split("")
    var pair = {'[':']','{':'}','(':')'}
    var queue = []
    for (var i = 0; i < data.length; i++) {
        var start = data[i].match(/[\{\(\[]/)
        if(start != null){
            queue.push(pair[start.input])
        }else {
            var end = queue.pop()
            if(end != data[i]){
                return 0
            }
        }
    }
    return 1
}

function solution(S) {
    //新增檢查邏輯
    if(S.length % 2 == 1 || S.match(/^[\}\)\]]/) != null){
        return 0
    }
    var data = S.split("")
    var pair = {'[':']','{':'}','(':')'}
    var queue = []
    for (var i = 0; i < data.length; i++) {
        var start = data[i].match(/[\{\(\[]/)
        if(start != null){
            queue.push(pair[start.input])
        }else {
            var end = queue.pop()
            if(end != data[i]){
                return 0
            }
        }
    }
    //一定要全部都有成對
    if(queue.length > 0){
        return 0
    }
    return 1
}