Question

Array with Pointers

Find Continuous Sub-Array C++

Problem: Given an unsorted array A of size N of non-negative integers, find a continuous sub-array which adds to the given number. Declare dynamic arrays and use only pointers syntax
(no [ ]’s or (ptr+i) stuff.

    Input will be the number of input values to enter followed by the sum to compare with. Print out the continuous sub-array of values that are equal to sum or the message ‘No sum found’. There may be more than one sub-array to be found in a given input.

Example:

Input: 6 10     First number represents 6 values to enter and 10 is the sum.

3 5 8 2 3 5         6 input values for the array.

Output: 8 2   and 2 3 5     these are continuous sub-array values that sum to 10

Your input data sets: I would create an input file for the following.

6 10

3 5 8 2 3 5

8 20

5 10 -3 3 10 -3 4 14

6 12

8 5 3 3 7 7

9 15

3 8 4 3 10 2 3 8 2

6 12

8 5 3 3 4 5

30 20

10 12 8 5 15 5 10 8 2 4 6 9 1 7 6 3 2 7 15 18 20 5 3 2 7 9 3 2 18 5

                                              

Answer 1

#include <iostream>

using namespace std;

void subarray(int arr[], int n)

{

  int MAX_start = 0;

  int max_end = 0;

  int start = 0, end = 0;

  int borrow = 0;

  for (int i = 0; i < n; i++)

  {

    max_end = max_end+ arr[i];

    if (max_end < 0)

    {

      max_end = 0;  

      borrow = i + 1;

    }

  if (MAX_start < max_end)

    {

      MAX_start = max_end;

      start = borrow;

      end = i;

    }

  }

  cout << "The sum of contiguous subarray is " <<

      MAX_start << endl;

  cout << "The contiguous subarray is";

  for (int i = start; i <= end; i++)

    cout << arr[i] << " ";

}

// main function

int main()

{

  int arr[] = { 6,10 };

  int n = sizeof(arr)/sizeof(arr[0]);

  subarray(arr, n);

  return 0;

}

PLEASE GIVE A THUMBS UP!!!!!!!!!