please give pseudocode or java code CS algorithms Use the following ideas to dev

Question

please give pseudocode or java code

CS algorithms Use the following ideas to develop a nonrecursive, linear-time algorithm for the maximum-subarray problem. Start at the left end of the array, and progress toward the right, keeping track of the maximum subarray seen so far. Knowing a maximunm subarray of A[l . . j], extend the answer to find a maximum subarray ending at in- dex j +1 by using the following observation: a maximum subarray of A[1· +1 is either a maximum subarray of A[i.. j] or a subarray Alij1], for some l ij + 1. Determine a maximum subarray of the form Ali..j + 1 in constant time based on knowing a maximum subarray ending at index j

Explanation / Answer

please upvote if you find solution useful.
Java
_____________________________________________________________________

import java.io.*;
// Java program to print largest contiguous array sum
import java.util.*;

class Kadane
{
public static void main (String[] args)
{
int [] a = {-2, -3, 4, -1, -2, 1, 5, -3};
System.out.println("Maximum contiguous sum is " +
maxSubArraySum(a));
}

static int maxSubArraySum(int a[])
{
int size = a.length;
int max_so_far = Integer.MIN_VALUE, max_ending_here = 0;

for (int i = 0; i < size; i++)
{
max_ending_here = max_ending_here + a[i];
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
if (max_ending_here < 0)
max_ending_here = 0;
}
return max_so_far;
}
}

___________________________________________________________________________________________
C++

#include<iostream>
using namespace std;

// Function to find contiguous sub-array with the largest sum
// in given set of integers
int kadane(int arr[], int n)
{
// stores maximum sum sub-array found so far
int max_so_far = 0;

// stores maximum sum of sub-array ending at current position
int max_ending_here = 0;

// traverse the given array
for (int i = 0; i < n; i++)
{
// update maximum sum of sub-array "ending" at index i (by adding
// current element to maximum sum ending at previous index i-1)
max_ending_here = max_ending_here + arr[i];

// if maximum sum is negative, set it to 0 (which represents
// an empty sub-array)
max_ending_here = max(max_ending_here, 0);

// update result if current sub-array sum is found to be greater
max_so_far = max(max_so_far, max_ending_here);
}

return max_so_far;
}

// main function
int main()
{
int arr[] = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
int n = sizeof(arr)/sizeof(arr[0]);

cout << "The sum of contiguous sub-array with the largest sum is " <<
kadane(arr, n);

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.