这段代码可以进一步优化吗？

Question

我尝试过的：

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        int A, B;
        long K;
        Scanner input = new Scanner(System.in);
        int N = input.nextInt();
        int M = input.nextInt();

        long[] array = new long[N];

        for(long i=1; i<=M; i++) {
            A = input.nextInt();
            B = input.nextInt();
            K = input.nextInt();
            for(int j=A; j<=B; j++) {
                array[j-1] += K;
            }
        }
       long max = 0;
       for(int i=1; i<array.length; i++) {
            if(max < array[i]) {
                max = array[i];
            }
        }
        System.out.println(max);
    }
}

问题是：前 7 个案例是正确的，除了最后 7 个 - “因超时而终止”。

Answer 1

使 K 成为一个 int，而不是 long...它不会被分配一个比 int 更大的值...K = input.nextInt() 方法 returns 一个 int。 ..

Answer 2

在Java8中使用IntStream会加速操作。

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.IntStream;

public class StreamUse {

    public static void main(String[] args) {

        // some file that contains the input
        File file = new File("C:\Users\Yahya\Desktop\input.txt");
        Scanner input;

        long startTime, endTime; // just to test how long time it will take

        try {
            input = new Scanner(file);

            // read the first line which contains the number of elements and operations
            String firstLine = input.nextLine(); 
            // parse the line (the first is N)
            int N = Integer.parseInt(firstLine.split(" ")[0]);
            // you don't really need M because it'll read the entire file
            //int M = Integer.parseInt(firstLine.split(" ")[1]);

             startTime = System.currentTimeMillis();
             long[] array = new long[N+2];

             // fill the array with zeros
             IntStream.range(0, N).forEach(i -> array[i]=0);

             // while the file contains more input
             while(input.hasNextLine()){
                 // read every line and parse it
                 String[] line = input.nextLine().split(" ");

                 int A = Integer.parseInt(line[0]);
                 int B =Integer.parseInt(line[1]);
                 long K = Long.parseLong(line[2]);

                 //increment the elements that specified by range
                 // of indices by K
                 IntStream.rangeClosed(A, B).forEach(i -> array[i]+=K); 
             }
             // return the max if any
             Arrays.stream(array).max().ifPresent(System.out::println);

             endTime = System.currentTimeMillis();

             System.out.println("Time Consumed: " + (endTime - startTime) + " Millisecond");

        } catch (FileNotFoundException e) {
            System.out.println("Could not find the file");
        }   
    }
}

鉴于此输入格式：

First line will contain two integers N and M separated by a single space. Next M lines will contain three integers a, b and k separated by a single space.

还有一个文件内容（注意数字有多大）：

10000 3
1 2000 100000
1500 5000 200000
4000 9900 999999

测试

1199999
Time Consumed: 281 Millisecond

Answer 3

朋友，我解决了你给出的问题，现在终于解决了：查看优化代码，我对这段代码采取了不同的方法。我所做的是存储给定的更改，然后应用它们，如果您不明白，请发表评论。它的工作我已经测试过。

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

  public static void main(String[] args) {

      Scanner scn = new Scanner (System.in);

      int N = scn.nextInt();
      int M = scn.nextInt();

      Long [] hello = new Long [N+2];

      for (int pro = 0; pro < M ; pro++){
         int a = scn.nextInt();
         int b = scn.nextInt();
         long k = scn.nextInt();
         if (hello[a] == (Long) null) hello[a] = (long)0;
         if (hello[b+1] == (Long) null) hello [b+1] = (long)0;
         hello[a] += k;
         hello [b+1] += k * -1;

      }

    //compile the arry and find the largest
      boolean editLargest = true;
      Long largest = hello[0];
      long eK = 0;
      for (int pro = 0; pro < hello.length-1 ; pro++){
          if (hello [pro] == (Long)null)continue;
          if (editLargest){
                largest = hello[pro];
                editLargest = false;
          }
          eK += hello[pro];
          if (largest < eK) largest = eK;
      }
      System.out.println (largest);

  }
}

查看屏幕排序 https://i.stack.imgur.com/lzqAq.png

这段代码可以进一步优化吗？

Can this code be optimized any further than this?

java

time

complexity-theory