Java Program to Find the Maximum Subarray Sum using 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 (n²).

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

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Note: Join free Sanfoundry classes at Telegram or Youtube

If you wish to look at all Java Programming examples, go to Java Programs.

« Prev - Java Program to Find Peak Element of an Array using Binary Search

» Next - Java Program to Find the Maximum Subarray Sum using Divide and Conquer

Next Steps:

Get Free Certificate of Merit in Java Programming
Participate in Java Programming Certification Contest
Become a Top Ranker in Java Programming
Take Java Programming Tests
Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Related Posts:

Practice Programming MCQs
Practice Information Technology MCQs
Buy Java Books
Apply for Information Technology Internship
Buy Programming Books

Recommended Articles: