Java Program to find the maximum subarray sum O(n^2) time(naive method)

This is a Java Program to find maximum subarray sum of an array. A subarray is a continuous portion of an array. The time complexity of the following program is O (n2).

Here is the source code of the Java program to find maximum subarray sum. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

/*
 * Java Program to Find the maximum subarray sum O(n^2)time 
 * (naive method)
 */
import java.util.Scanner;
 
public class MaxSubarraySum1
{
    public static void main(String[] args) 
    {
        Scanner scan = new Scanner(System.in);
        System.out.println("Enter number of elements in array");
        int N = scan.nextInt();
        int[] arr = new int[ N ];
        /* Accept N elements */
        System.out.println("Enter "+ N +" elements");
        for (int i = 0; i < N; i++)
            arr[i] = scan.nextInt();
        System.out.println("Max sub array sum  = "+ max_sum(arr));
    }
    public static int max_sum(int[] arr)
    {
        int N = arr.length, max = Integer.MIN_VALUE;
        for (int i = 0; i < N; i++)
        {
            int sum = 0;
            for (int j = i; j < N; j++)
            {
                sum += arr[j];
                if (sum > max)
                    max = sum;
            }
        }
        return max;    
    }
}
Enter number of elements in array
8
Enter 8 elements
-2 -5 6 -2 -3 1 5 -6
Max sub array sum  = 7

Related posts:

HashSet trong Java hoạt động như thế nào?
Spring Boot - Eureka Server
Thực thi nhiều tác vụ cùng lúc như thế nào trong Java?
Java Program to Give an Implementation of the Traditional Chinese Postman Problem
Spring Boot - Internationalization
Write/Read cookies using HTTP and Read a file from the internet
REST Web service: Basic Authentication trong Jersey 2.x
Spring Boot - OAuth2 with JWT
Spring Security Registration – Resend Verification Email
Java Program to Implement LinkedHashMap API
Request a Delivery / Read Receipt in Javamail
Spring Cloud Series – The Gateway Pattern
Map to String Conversion in Java
Java Program to Implement Interval Tree
TreeSet và sử dụng Comparable, Comparator trong java
Java Program to Generate All Possible Subsets with Exactly k Elements in Each Subset
Mockito and JUnit 5 – Using ExtendWith
Java Program to Implement Gift Wrapping Algorithm in Two Dimensions
Java Program to Implement Miller Rabin Primality Test Algorithm
HttpClient Basic Authentication
Ép kiểu trong Java (Type casting)
Java Program to Implement RenderingHints API
Java Program to Perform integer Partition for a Specific Case
Disable Spring Data Auto Configuration
XML Serialization and Deserialization with Jackson
Java Program to Check Cycle in a Graph using Graph traversal
Java Program to Perform Matrix Multiplication
A Quick Guide to Spring MVC Matrix Variables
Deque và ArrayDeque trong Java
Spring Boot - Tracing Micro Service Logs
Rest Web service: Filter và Interceptor với Jersey 2.x (P2)
Introduction to the Java NIO2 File API