MagicLen

題目描述

陣列是一個非常簡單的資料結構，可以用來儲存資料。舉例來說，陣列可以儲存一個班級裡所有學生的學號，也可以儲存世界上所有國家的名稱。

您可以寫出以下的程式來建立一個能儲存10個整數的陣列：

int[] myList = new int[10];

這個題目將會測試您對Java陣列的認知。

您將會得到一個擁有n個整數的陣列。若所有在子陣列中的整數相加之後是負數的，則稱這個子陣列為「Negative」。計算輸入的陣列擁有幾個「Negative」的子陣列。

子陣列由(主)陣列連續的元素組成。舉例來說，若陣列為{1,2,3,4,5}，則{1}、{1,2,3}、{2,3,5}、{1,2,3,5}都算是這個陣列的子陣列。{1,2,5}不是子陣列，因為它在陣列{1,2,3,4,5}中並沒有連續。

原題網址

https://www.hackerrank.com/challenges/java-1d-array-easy

輸入格式

第一行包含一個整數n，最大值為100。接下來的一行有n個使用空格隔開的整數，範圍在-10000到10000之間(包含-10000和10000)。

輸出格式

輸出陣列中有多少個「Negative」的子陣列。

範例輸入

5
1 -2 4 -5 1

範例輸出

9

額外解釋

以下是「Negative」的子陣列索引範圍：

[0:1]
[0:3]
[0:4]
[1:1]
[1:3]
[1:4]
[2:3]
[3:3]
[3:4]

索引值從0開始。

解題概念

先實作出一個用來計算陣列指定索引範圍內元素加總的sum方法，接著再撰寫巢狀迴圈來產生所有子陣列的索引範圍。

參考答案

import java.util.Scanner;

public class Solution {

    public static void main(final String[] args) {

        final Scanner sc = new Scanner(System.in);
        final int n = sc.nextInt();
        final int[] a = new int[n];
        for (int i = 0; i < n; ++i) {
            a[i] = sc.nextInt();
        }

        int counter = 0;
        for (int length = 1; length <= n; ++length) {
            final int end = n - length;
            for (int start = 0; start <= end; ++start) {
                if (sum(a, start, length) < 0) {
                    ++counter;
                }
            }
        }
        System.out.println(counter);
    }

    private static int sum(final int[] a, final int start, final int length) {
        int sum = 0;
        for (int i = 0; i < length; ++i) {
            sum += a[start + i];
        }
        return sum;
    }
}