This is a very interesting problem and can be a bit tricky for a beginner in programming. This problem required a good understanding of the Array concept.

The following 3 approaches are discussed from brute force -> better -> best.

let's get started.

1st Approach Using nested loops(brute Force)

use 2 nested loops to traverse through the array one by one visiting each element twice. using the 3rd nested loop to calculate the sum and store it for further comparison. If it's confusing wait till you get a sneak peek into the code.

---

 public static void main(String[] args) {
        int[] arr = new int[] {2,-4,6,8,-10}; // given array
        int sum = 0; 
        int maxSum = Integer.MIN_VALUE;
        for(int start = 0; start < arr.length; start++) {
            for(int i = start; i < arr.length; i++) {
                for(int j = start; j <= i; j++) {
                    sum += arr[j]; // calucate sum
                }
                if(sum > maxSum) maxSum = sum; //compare sum with the max sum
                sum = 0;
            }
        }
        System.out.println("maxSum: " + maxSum);//output
    }

output

14

Time Complexity: O(n^3)
Space Complexity: O(1)

---

2nd Approach uses the prefix Sum array or helper array

we will use a second array to store the sum of numbers occurring before that particular index and will continue to store the sum till the last index.
then we will use that prefix sum to calculate that sum between 2 particular indexes. If it's confusing wait till you get a sneak peek into the code.

---

import java.util.Scanner;

public class prefixSumApporchMaxSum {

    static void subArrSum(int arr[]) {
// creating a prefix sum
        int[] prefix = new int[arr.length];
        prefix[0] = arr[0];
        for (int i = 1; i < arr.length; i++) {
            prefix[i] = prefix[i - 1] + arr[i];
        }
// calculating sum 
        int currSum = 0;
        int maxSum = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j < arr.length; j++) {
                currSum = i == 0 ? prefix[j] : prefix[j] - prefix[i - 1];
            }
            if (currSum > maxSum)
                maxSum = currSum;
        }
        System.out.println("max subarray Sum: " + maxSum);
    }

input

5 [3,6,-2,1,5]

output

13

Time Complexity: O(n^2)
Space Complexity: O(n) because we are using an array to store preFixSum

---

3rd and most optimized Approach uses Kadane's algorithm.

Kadane's algorithm has a simple idea.

• Bigger +VE + Smaller -VE = +VE

• Bigger -VE + Smaller +VE = -VE

we just have to reset our sum to ZERO if by adding a number makes it less then ZERO.

static int kadaneSumArraySum(int arr[]) {
        int currSum = 0;
        int maxSum = Integer.MIN_VALUE;
        for(int i = 0; i < arr.length; i++) {
            if(currSum + arr[i] < 0) {// if sum goes below zero
                currSum = 0;
            }
            else {
                currSum += arr[i]; 
            }
            if(currSum > maxSum) {
                maxSum = currSum;
            }
        }
        return maxSum;
   }

These were the solution to a very famous problem.

HOPE I ADDED VALUE TO YOUR LEARNING. SEE U!!