Bài toán tìm mảng con có trọng số lớn nhất trong C++

» Nhân hai số nguyên lớn
» Nhân hai sô nguyên lớn, Chia hai số nguyên lớn, Cộng hai số nguyên lớn, Trừ hai số nguyên lớn trong C++
» Xử Lý Tín Hiệu Số
» Giáo trình Vi xử lý - vi xử lý 8086 - vi xử lý 8088
» An Toàn Dữ Liệu, An toàn và bảo mật hệ thống thông tin
» Bài Tập Ngôn Ngữ Lập Trình LISP - JAVA

Giới Thiêu:

#include <iostream.h>
#include <conio.h>
#include <stdio.h>
int a[10000];
int Max = 0  ;              // luu lai tong lon nhat
int index1, index2 ;     // de luu lai vi tri cua mang con.
void DoLeft( int *, int , int);
void DoRight( int *, int , int);
/* Duyet tu trai sang phai */
void DoLeft( int *a, int left, int right)
  {
    int sumleft = 0 ;
    int i = left;
    for( i = left; i<= right; i++ )
       {
     if( sumleft + a[i] <= 0 ) break ;
     sumleft += a[i];
       }
    if( sumleft > Max )
       {
       Max = sumleft;
       index1 = left;
       index2 = i - 1;
       }
    if( i+1 <= right ) DoLeft( a, i+1, right);
    if( i> left ) DoRight(a,left,i-1) ;
  }

/*  Duyet nguoc lai tu phai qua trai  */
void DoRight( int *a, int left, int right)
  {
    int sumright = 0 ;
    int i = right;
    for( i = right; i >= left; i-- )
       {
         if( sumright + a[i] <= 0 ) break ;
         sumright += a[i];
       }
    if( sumright > Max )
       {
       Max = sumright;
       index1 = i+1;
       index2 = right;
       }
    if ( i <= left ) return ;               // Day la dieu kien dung
    DoRight(a,left,i-1) ;
    if( i+1 <= right ) DoLeft( a, i+1, right);
  }

int main()
 {
  int n;
  printf("\nNhap so phan tu mang n= "); scanf("%d",&n);

  for(int i= 0; i < n; i++)
  {
  printf("a[%d]= ",i); scanf("%d",&a[i]);
  printf("\n");
  }
  DoLeft( a, 0, n);
  cout << " Mang con co tong cac phan tu lon nhat la ";
  cout << " a[" << index1 <<"..." << index2 << "]\n";
  cout << " Tong = " << Max;
  getch();
  return 0 ;
 }

Download Now